2676: 队爷的 Au Plan
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
队爷为了变得越来越神,他给自己制定了 n 个任务,编号为 1,2,...,n。队爷在完成这些任务之前有一个初始兴奋值 m,每个任务都有一个难度值 hard[i],且对于任何 i>j,有 hard[i]>hard[j],队爷完成第 i 个任务,兴奋值至少会减少 hard[i],第 i 任务完成之后,队爷会受到鼓舞,兴奋值又会增加 s[i],每个任务只完成一次。队爷可以一次完成所有剩余的难度值不超过现有兴奋度的任务,这样只会消耗那个最大的难度值。现在队爷想知道完成这 n 个任务之后,他的最大兴奋值为多少。
输入
第一行 2 个整数 n,m,如题意。
第二行 n 个整数,第 i 个为 hard[i]。
第三行 n 个整数,第 i 个为 s[i]。
输出
一个整数,为完成这 n 个任务之后的最大兴奋值。
样例输入 复制
5 5
2 4 5 7 9
4 4 3 6 5样例输出 复制
14提示
第一次完成前 2 个任务,兴奋值为 9;
第二次完成后 3 个任务,兴奋值为 14。
对于 30%的数据,1<=n<=2000
对于另外 20%的数据,所有的 s[i]之和小于 200000;
对于 100%的数据,1<=n<=200000,数据保证所有任务都能完成。