Minimum Sum of Maximums

Time limit2sMemory limit1024 MB

Summary

Given a line of tiles with some fixed positions, the task is to permute the free tiles to minimize the sum of pairwise maximums of adjacent tiles.

Level: Medium7 of 10
Topics: Greedy, Sorting, Dynamic programming
Solved: No attempts yet

Problem

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. They are the tiles 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 the sum of the larger ugliness value over every consecutive pair of tiles: $\sum_{i=1}^{N-1}\max(a_i,a_{i+1})$ . She can swap any two tiles that are both not stuck in place, and she can perform this operation any number of times.

Determine the minimum total ugliness Bessie can achieve by performing the operations optimally.

Input

The first line contains $N$ and $K$ .

The second line contains $a_1, \dots, a_N$ .

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

Output

Output the minimum possible total ugliness.

Examples4

Example 1
Input
```
3 0
1 100 10
```
Expected output
```
110
```
Example 2
Input
```
3 1
1 100 10
3
```
Expected output
```
110
```
Example 3
Input
```
3 1
1 100 10
2
```
Expected output
```
200
```
Example 4
Input
```
4 2
1 3 2 4
2 3
```
Expected output
```
9
```