题目描述

卡卡西果然不负众望，很快就将“园区最受欢迎指数”问题迎刃而解，此时，天空中出现一道金光，照的小朋友们都睁不开眼睛，卡卡西发现所有小朋友手上的动物园门票都慢慢变的清晰起来，并且升至空中，聚集在一起，形成一个巨大的彩虹形状的大桥……这是梦吗？小朋友们都不敢相信自己的眼睛，努力的揉着眼睛。是的，是真的！这些手中的门票，合在一起变成了一座七彩桥，来迎接小朋友们去动物园呢！卡卡西带着小朋友们，相继和植物园的叔叔阿姨们再见，然后有条不紊的走上了桥…… 没多久功夫，动物园就到了，卡卡西和小伙伴们走下了大桥。可是好奇怪啊，本该热闹非凡的动物园怎么安安静静的，什么活动都没有，大门也紧锁着。小朋友们的心里有点害怕，仔细观察了下，卡卡西在大门外发现了一张告示，上面贴着一道题目，原来动物园园长被困在了迷宫里，由神秘的绿巨人守卫着，他出了一道题目，如果有人能破解此题，就释放园长！题目是这样的：假设现在要从城堡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