#1224. [合肥市 2015] 最多奖励(win)

[合肥市 2015] 最多奖励(win)

题目描述

卡卡西果然不负众望,很快就将“园区最受欢迎指数”问题迎刃而解,此时,天空中出现一道金光,照的小朋友们都睁不开眼睛,卡卡西发现所有小朋友手上的动物园门票都慢慢变的清晰起来,并且升至空中,聚集在一起,形成一个巨大的彩虹形状的大桥……这是梦吗?小朋友们都不敢相信自己的眼睛,努力的揉着眼睛。是的,是真的!这些手中的门票,合在一起变成了一座七彩桥,来迎接小朋友们去动物园呢!卡卡西带着小朋友们,相继和植物园的叔叔阿姨们再见,然后有条不紊的走上了桥…… 没多久功夫,动物园就到了,卡卡西和小伙伴们走下了大桥。可是好奇怪啊,本该热闹非凡的动物园怎么安安静静的,什么活动都没有,大门也紧锁着。小朋友们的心里有点害怕,仔细观察了下,卡卡西在大门外发现了一张告示,上面贴着一道题目,原来动物园园长被困在了迷宫里,由神秘的绿巨人守卫着,他出了一道题目,如果有人能破解此题,就释放园长!题目是这样的:假设现在要从城堡A经过若干障碍到达城堡B,每经过一个障碍都要消耗一定的能量,但也有一定的奖励。人们可以经过传送门到达任意障碍处,那么在有限的能量内,该如何选择障碍,使得到达城堡B时获得的奖励最多。 卡卡西咬咬牙,坚定的说:“小伙伴们,咱们一定要努力破解此题,救出园长!”聪明的小朋友们,你们能帮忙解救园长吗?

输入输出格式

输入

输入数据有3行,第1行有2个用空格分开的数,表示出发时的能量a和障碍数目n;第2行有n个用空格分开的数,其中,第i个数表示清除第i个障碍所需能量;第3行有n个用空格分开的数,其中,第i个数表示清除第i个障碍获得的奖励。

输出

最多的奖励。

输入输出样例

样例

输入1

10 5
2 3 4 2 5
1 7 4 3 4

输出1

14

数据范围/约定

1s, 256MB.

0<a<=1000; 0<n<=100; 0<障碍所需能量,奖励<100