问题 23654 --【NOIP2010】乌龟棋

23654: 【NOIP2010】乌龟棋

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 7
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][92kb]

题目描述

 

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

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

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

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

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

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

 

输入

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

输出

 

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

样例输入

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

样例输出

73

提示

 


【输入输出样例说明】



小明使用爬行卡片顺序为11312,得到的分数为6+10+14+8+18+17=73。注意,由于起点是1,所以自动获得第1格的分数6




来源

[提交][状态]