题目描述

题目来自 USACO 2024 February Contest, Platinum Problem 2. Minimum Sum of Maximums

Bessie 有一行 $N$（$2 \le N \le 300$）块瓷砖，依次具有丑陋度 $a_1, a_2, \ldots, a_N$（$1 \le a_i \le 10^6$）。其中 $K$（$0 \le K \le \min(N,6)$）块瓷砖卡住了；具体地，索引为 $x_1, \ldots, x_K$（$1 \le x_1 < x_2 < \ldots < x_K \le N$）的瓷砖。

Bessie 想要最小化瓷砖的总丑陋度，其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和；即 $\sum_{i=1}^{N-1} \max(a_i, a_{i+1})$。她可以任意次执行以下操作：选择两块均未卡住的瓷砖，并交换它们。

求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。

输入格式

输入的第一行包含 $N$ 和 $K$。

第二行包含 $a_1, \ldots, a_N$。

第三行包含 $K$ 个索引 $x_1, \ldots, x_K$。

输出格式

输出最小可能的总丑陋度。

样例 1

输入

3 0
1 100 10

输出

110

Bessie 可以交换第二块和第三块瓷砖，使得 $a=[1,10,100]$，达到总丑陋度 $\max(1,10) + \max(10,100) = 110$。或者，她也可以交换第一块和第二块瓷砖，使得 $a=[100,1,10]$，同样达到总丑陋度 $\max(100,1) + \max(1,10) = 110$。

样例 2

输入

3 1
1 100 10
3

输出

110

Bessie 可以交换第一块和第二块瓷砖，使得 $a=[100,1,10]$，达到总丑陋度 $\max(100,1) + \max(1,10) = 110$。

样例 3

输入

3 1
1 100 10
2

输出

200

瓷砖的初始总丑陋度为 $\max(1,100) + \max(100,10) = 200$。Bessie 只允许交换第一块和第三块瓷砖，这并不能使她能够减少总丑陋度。

样例 4

输入

4 2
1 3 2 4
2 3

输出

9

数据范围与提示

• 测试点 5：$K=0$。
• 测试点 6-7：$K=1$。
• 测试点 8-12：$N \le 50$。
• 测试点 13-24：没有额外限制。