Minimum Sum of Maximums timer 1s memory 1024MB

Bessie has N (2\le N\le 300) tiles in a line with ugliness values a_1, a_2, \dots, a_N in that order (1\le a_i\le 10^6). K (0\le K\le \min(N,6)) of the tiles are stuck in place; specifically, those at indices x_1,\dots, x_K (1\le x_1 < x_2<\dots< x_K\le N).

Bessie wants to minimize the total ugliness of the tiles, which is defined as the sum of the maximum ugliness over every consecutive pair of tiles; that is, \sum_{i=1}^{N-1}\max(a_i,a_{i+1}). She is allowed to perform the following operation any number of times: choose two tiles, neither of which are stuck in place, and swap them.

Determine the minimum possible total ugliness Bessie can achieve if she performs operations optimally.