Minimum Sum of Maximums

문제

Bessie has $NN$ ($2\le N\le 3002\backslash le\; N\backslash le\; 300$) tiles in a line with ugliness values $a_1,a_2,\dots ,a_{N}a\_1,\; a\_2,\; \backslash dots,\; a\_N$ in that order ($1\le a_i\le {10}^{6}1\backslash le\; a\_i\backslash le\; 10^6$). $KK$ ($0\le K\le \min (N,6)0\backslash le\; K\backslash le\; \backslash min(N,6)$) of the tiles are stuck in place; specifically, those at indices $x_1,\dots ,x_{K}x\_1,\backslash dots,\; x\_K$ ().

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})\backslash sum\_\{i=1\}^\{N-1\}\backslash 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.

입력

The first line contains $NN$ and $KK$.

The next line contains $a_1,\dots ,a_{N}a\_1,\backslash dots,a\_N$.

The next line contains the $KK$ indices $x_1,\dots ,x_{K}x\_1,\backslash dots,x\_K$.

출력

Output the minimum possible total ugliness.

3 0
1 100 10

110

3 1
1 100 10
3

110

3 1
1 100 10
2

200

4 2
1 3 2 4
2 3

9