题目描述
贝西有 N 块瓷砖排成一行,其中 2≤N≤300。第 i 块瓷砖的丑陋值为 ai,满足 1≤ai≤106。
其中 K 块瓷砖被固定在了位置上,0≤K≤min(N,6)。固定位置按递增顺序给出,满足 1≤x1<⋯<xK≤N。
贝西想要最小化所有瓷砖的总丑陋值,这个总丑陋值被定义为每对连续瓷砖中最大丑陋值的和,即 ∑i=1N−1max(ai,ai+1) 。她可以进行任意次数的以下操作:选择两块没有被固定的瓷砖,并交换它们的位置。
我们需要确定,如果贝西以最优的方式进行操作,她能够达到的最小总丑陋值是多少。
输入格式
第一行包含 N 和 K 。
第二行包含瓷砖的丑陋值 a1,…,aN 。
第三行包含被固定的瓷砖的索引 x1,…,xK。K=0 时没有索引。
输出格式
输出最小可能的总丑陋值。
样例
3 0
1 100 10
110
贝西可以交换第二块和第三块瓷砖,使得 a=[1,10,100] ,达到总丑陋值 max(1,10)+ max(10,100)=110 。
另外,她也可以交换第一块和第二块瓷砖,使得 a=[100,1,10] ,同样达到总丑陋值
max(100,1)+max(1,10)=110。
3 1
1 100 10
3
110
贝西可以交换第一块和第二块瓷砖,使得 a=[100,1,10] ,达到总丑陋值 max(100,1)+max(1,10)= 110 。
3 1
1 100 10
2
200
瓷砖的初始总丑陋值是 max(1,100)+max(100,10)=200 。 贝西只允许交换第一块和第三块瓷砖,这使得她无法降低总丑陋值。
4 2
1 3 2 4
2 3
9
数据范围
- Input 5: K=0
- Inputs 6-7: K=1
- Inputs 8-12: N≤50
- Inputs 13-24: No additional constraints