当前没有测试数据。

一、Problem Name

Minimum Sum of Maximums

二、Problem Description

Bessie has $N$ ($2\leq N\leq300$) tiles in a line with ugliness values $a_1,a_2,\cdots,a_N$ in that order ($1\leq a_i\leq10^6$). $K$ ($0\leq K\leq\min(N,6)$) of the tiles are stuck in place; specifically, those at indices $x_1,\cdots,x_K$ ($1\leq x_1<x_2<\cdots<x_K\leq 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.

三、Input Format (input arrives from the terminal / stdin)

1. The first line contains $N$ and $K$.
2. The next line contains $a_1,\cdots,a_N$.
3. The next line contains the $K$ indices $x_1,\cdots,x_K$.

四、Output Format (print output to the终端 / stdout)

Output the minimum possible total ugliness.

五、Sample Input and Output

Sample Input 1

3 0
1 100 10

Sample Output 1

110

Explanation: 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 2

3 1
1 100 10
3

Sample Output 2

110

Explanation: 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

3 1
1 100 10
2

Sample Output 3

200

Explanation: 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

4 2
1 3 2 4
2 3

Sample Output 4

9

六、Scoring Rules

1. Input 5: $K = 0$.
2. Inputs 6 - 7: $K = 1$.
3. Inputs 8 - 12: $N\leq50$.
4. Inputs 13 - 24: No additional constraints.

Problem credits: Benjamin Qi.