P10197 [USACO24FEB] Minimum Sum of Maximums P

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

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

##### For Sample 1: 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$. ##### For Sample 2: Bessie could swap the first and second tiles so that $a=[100,1,10]$, achieving total ugliness $\max(100,1)+\max(1,10)=110$. ##### For Sample 3: 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. #### SCORING: - Input 5: $K=0$ - Inputs 6-7: $K=1$ - Inputs 8-12: $N\le 50$ - Inputs 13-24: No additional constraints