#2593. 「NOIP2010」乌龟棋

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行 NNN 个格子,每个格子上一个分数(非负整数)。棋盘第 111 格是唯一的起点,第 NNN 格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 MMM 张爬行卡片,分成 444 种不同的类型(MMM 张卡片中不一定包含所有 444 种类型的卡片,见样例),每种类型的卡片上分别标有 111222333444 四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次。

游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?

输入格式

输入文件的每行中两个数之间用一个空格隔开。

111222 个正整数 NNNMMM,分别表示棋盘格子数和爬行卡片数;

222NNN 个非负整数, a1,a2,⋯⋯,aNa_1, a_2, \cdots\cdots, a_Na1,a2,,aN ,其中 aia_iai 表示棋盘第 iii 个格子上的分数;

333MMM 个整数, b1,b2,⋯⋯,bMb_1,b_2, \cdots\cdots, b_Mb1,b2,,bM ,表示 MMM 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 MMM 张爬行卡片,即 N1=Mi=1bi

输出格式

输出只有 111 行,111 个整数,表示小明最多能得到的分数。

样例

样例输入 1

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

样例输出 1

73

样例说明 1

小明使用爬行卡片顺序为 11312 ,得到的分数为 6+10+14+8+18+17=736+10+14+8+18+17=736+10+14+8+18+17=73

注意,由于起点是 111,所以自动获得第 111 格的分数 666

样例输入 2

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

样例输出 2

455

数据范围与提示

对于30%30\%30% 的数据有 N≤30N\leq 30N30M≤12M\leq 12M12

对于50%50\%50% 的数据有 N≤120N\leq 120N120M≤50M\leq 50M50,且 444 种爬行卡片,每种卡片的张数不会超过 202020

对于100%100\%100% 的数据有1≤N≤3501\leq N\leq 3501N3501≤M≤1201\leq M\leq 1201M120,且 444 种爬行卡片,每种卡片的张数不会超过 4040400≤ai≤1000 \leq a_i \leq 1000ai1001≤i≤N1 \leq i \leq N1iN1≤bi≤41 \leq b_i \leq 41bi41≤i≤M1 \leq i \leq M1iM

输入数据保证 N1=Mi=1bi