问题 3695 --智力大冲浪

3695: 智力大冲浪

时间限制: 1 Sec  内存限制: 256 MB
提交: 7  解决: 3
[提交][状态][讨论版][命题人:]

题目描述

比赛时间分为n(n≤5000)个时段,给出了很多小 游戏,每个小游戏都必须在规定期限ti(1≤ti≤n)前完成。 如果一个游戏没能在规定期限前完成,则要从奖励 费m元中扣去一部分钱wi,wi为自然数,不同的游 戏扣去的钱是不一样的。当然每个游戏本身都很简 单,保证每个参赛者都能在一个时间段内完成,而 且必须从整时段开始。主持人只是想考考每个参赛 者如何安排组织自己做游戏的顺序。作为参赛者, 小伟很想赢得冠军,当然更想赢取最多的钱!注意:比赛绝对不会让参赛者赔钱! 

输入

第一行为m,表示一开始奖励给每位参赛者 的钱;

第二行为n,表示有n个小游戏;

第三行有n 个数,分别表示游戏1到n的规定完成期限;

第四行 有n个数,分别表示游戏1到n不能在规定期限前完 成的扣款数。 


输出

一个整数,表示赢取的最多的钱数

样例输入

10000 
7 
4 2 4 3 1 4 6 
40 70 10 50 30 60 20 

样例输出

9960

提示


对于 100%的数据



1<=n<=5000



1<=m<=5*10^5



1<=ti<=n



1<=wi<=1000

来源

[提交][状态]