F: 乌龟棋

1006: 乌龟棋

Time Limit: 2 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 2  Accepted: 1
[Submit][Status][Web Board]

Description

小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。
乌龟棋的棋盘是一行N个格子,每个格子上一个分数(非负整数)。棋盘第1格是唯一的起点,第N格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。
乌龟棋中M张爬行卡片,分成4种不同的类型(M张卡片中不一定包含所有4种类型的卡片,见样例),每种类型的卡片上分别标有1234四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次。
游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。
很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。
现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?

Input

多组测试数据。
输入文件的每行中两个数之间用一个空格隔开。
12个正整数NM,分别表示棋盘格子数和爬行卡片数。
2N个非负整数,a1,a2……aN,其中ai表示棋盘第i个格子上的分数。
3M个整数,b1,b2……bM,表示M张爬行卡片上的数字。
数据范围:1 <= N <= 350; ≤ ≤ 120; ≤ ai ≤ 100; ≤ bi ≤ 4; 每种卡片不超过40张;
数据保证:到达终点时刚好用光M张爬行卡片。

Output

每组输出一行,1个整数,表示小明最多能得到的分数。

Sample Input

9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1

Sample Output

73

[Submit][Status][Web Board]