## USACO 2024 February Contest, Platinum

## Problem 2. Minimum Sum of Maximums

Contest has ended.

**Log in to allow submissions in analysis mode**

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.

#### INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$ and $K$.The next line contains $a_1,\dots,a_N$.

The next line contains the $K$ indices $x_1,\dots,x_K$.

#### OUTPUT FORMAT (print output to the terminal / stdout):

Output the minimum possible total ugliness.#### 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

#### SCORING:

- Input 5: $K=0$
- Inputs 6-7: $K=1$
- Inputs 8-12: $N\le 50$
- Inputs 13-24: No additional constraints

Problem credits: Benjamin Qi