问题 6 臭美的 U 老师 提交列表 提交

普及/提高- · 标准输入 · 标准输出 · 0:00:01 · https://oj.wtf/6  复制分享链接 

描述

在某校,有一个臭美的U老师,他希望可以获得全校最漂亮奖。U老师能否成功?U老师的体重为x(1<=x<=200)千克,初始颜值为y(0<=y<=150),该校的讲台承重为z(200<=z<=1,000)千克。他有n(1<=n<=1,000)件漂亮的衣服,第i件衣服的重量为w[i](1<=w[i]<=2,000,000)克,并会给他增加f[j](1<=f[j]<=100,000,000,000)的颜值。他希望可以获得全校最漂亮奖,请问在不压垮讲台的情况下,他最高可以达到多少颜值?

对于100%的数据: 1<=x<=200; 0<=y<=150; 200<=z<=1,000; 1<=n<=1,000; 1<=n<=1,000; 1<=w[i]<=2,000,000; 1<=f[j]<=100,000,000,000。

输入

第一行有3个整数,分别为:x(体重),y(初始颜值),z(讲台承重)。 第二行有一个整数:n(衣服数量)。 第三行有n个整数,第i个表示第i件衣服的重量。 第四行有n个整数,第j个表示第j件衣服可以为U老师增加的颜值。

输出

输出最高可以达到多少颜值。

样例

输入

120 20 350
5
200 300 500 800 1200
10 12 50 40 80

输出

212

输入

160 100 500
10
200 950 800 500 1200 50 888888 200000 9000 59174
10 999 2220 25 550 1000 1 5201314 7758258 13995995995

输出

14008960471