Problem : 296 - 烏龜棋

Problem Statistics

Solved Member: 21　　Submission: 45　　User Tried: 22

Statement:

小明過生日的時候，爸爸送給他一副烏龜棋當作禮物。

烏龜棋的棋盤是一行N個格子，每個格子上一個分數（非負整數）。棋盤第1格是唯一的起點，第N格是終點，遊戲要求玩家控制一個烏龜棋子從起點出發走到終點。

烏龜棋中M 張爬行卡片，分成4 種不同的類型（M 張卡片中不一定包含所有4 種類型的卡片，見樣例），每種類型的卡片上分別標有1、2、3、4 四個數字之一，表示使用這種卡片後，烏龜棋子將向前爬行相應的格子數。遊戲中，玩家每次需要從所有的爬行卡片中選擇一張之前沒有使用過的爬行卡片，控制烏龜棋子前進相應的格子數，每張卡片只能使用一次。

遊戲中，烏龜棋子自動獲得起點格子的分數，並且在後續的爬行中每到達一個格子，就得到該格子相應的分數。玩家最終遊戲得分就是烏龜棋子從起點到終點過程中到過的所有格子的分數總和。

很明顯，用不同的爬行卡片使用順序會使得最終遊戲的得分不同，小明想要找到一種卡片使用順序使得最終遊戲得分最多。

現在，告訴你棋盤上每個格子的分數和所有的爬行卡片，你能告訴小明，他最多能得到多少分嗎？

Input:Output:

第1行2個正整數N和M，分別表示棋盤格子數和爬行卡片數。

第2行N個非負整數，a₁, a₂, ……, a_N，其中ai 表示棋盤第i 個格子上的分數。

第3行M個整數，b₁,b₂, ……, b_M，表示M 張爬行卡片上的數字。

保證到達終點時剛好用光M 張爬行卡片，即$N-1 = \sum\limits_{i=1}^{M} {bi}$

範圍限制：
對於30%的數據有1 ≤ N ≤ 30，1 ≤ M ≤ 12。

對於50%的數據有1 ≤ N ≤ 120，1 ≤ M ≤ 50，且4種爬行卡片，每種卡片的張數不會超過20。

對於100%的數據有1 ≤ N ≤ 350，1 ≤ M ≤ 120，且4種爬行卡片，每種卡片的張數不會超過40，0 ≤ ai ≤ 100，1 ≤ i ≤ N，1 ≤ bi ≤ 4，1 ≤ i ≤ M。

輸出一個數字表示小明最多能得到的分數。

Sample Input:Sample Output:

Sample #1:
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1

Sample #2:
13 8
4 96 10 64 55 13 94 53 5 24 89 8 30
1 1 1 1 1 2 4 1

Sample #1:
73

Sample #2:
455

HINT:

關於Sample #1:
小明使用爬行卡片順序為1，1，3，1，2，得到的分數為6+10+14+8+18+17=73。注意，由於起點是1，所以自動獲得第1格的分數6。

Source:

NOIP 2010 提高組

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1000ms	131072kb
0-2	1000ms	131072kb
1	1000ms	131072kb	10
2	1000ms	131072kb	10
3	1000ms	131072kb	10
4	1000ms	131072kb	10
5	1000ms	131072kb	10
6	1000ms	131072kb	10
7	1000ms	131072kb	10
8	1000ms	131072kb	10
9	1000ms	131072kb	10
10	1000ms	131072kb	10