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.

SAMPLE INPUT:

3 0
1 100 10

SAMPLE OUTPUT:

110

Bessie can swap the second and third tiles so that $a=[1,10,100]$, achieving total ugliness $\max(1,10)+\max(10,100)=110$. Alternatively, she could swap the first and second tiles so that $a=[100,1,10]$, also achieving total ugliness $\max(100,1)+\max(1,10)=110$.

SAMPLE INPUT:

3 1
1 100 10
3

SAMPLE OUTPUT:

110

Bessie could swap the first and second tiles so that $a=[100,1,10]$, achieving total ugliness $\max(100,1)+\max(1,10)=110$.

SAMPLE INPUT:

3 1
1 100 10
2

SAMPLE OUTPUT:

200

The initial total ugliness of the tiles is $\max(1,100)+\max(100,10)=200$. Bessie is only allowed to swap the first and third tiles, which does not allow her to reduce the total ugliness.

SAMPLE INPUT:

4 2
1 3 2 4
2 3

SAMPLE OUTPUT:

9

Problem credits: Benjamin Qi