塔子哥是一名工薪族,每个月工资刚刚够支付日常开支,因此他总是需要在超市购买实惠的商品。
有一天,他进入了一家超市,发现超市正在举行一场特殊活动。当塔子哥花费原价买了一件商品时,他可以用半价买下一件右边相邻的商品(也可以用原价购买,这样该商品右边的商品就有次享受半价的机会)。但如果塔子哥半价购买了一件商品,那么下一件右边相邻的商品只能原价购买。
塔子哥有一定的存款,但是他想尽可能多地购买他喜欢的商品,因此他想知道在限制总价不超过 x 的情况下,他最多可以获得多少喜爱度。
超市中有 n 个商品,每个商品的价格为偶数,第 i 个商品的价格为 ai ,塔子哥对它的喜爱度为 bi 。
现在,他想要买的商品的喜爱度总和尽可能大,但总价格不能超过 x 。你能帮帮他计算最大的喜爱度总和吗?
第一行输入两个正整数 n 和 x ,分别代表商品的数量,以及塔子哥初始的金额数。
第二行输入 n 个正整数 ai ,分别代表每个商品的价格。
第三行输入 n 个正整数 bi ,分别代表每个商品可以给塔子哥带来的喜爱度。
1≤n,x,ai≤1000
1≤bi≤109 保证所有的 ai 都是偶数。
一个整数,代表最终喜爱度之和的最大值。
输入
5 10
2 2 6 8 4
2 1 4 9 3
输出
13
输入
3 3
4 10 6
2 1 5
输出
0
样例解释
钱不够,无法购买任何物品。
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.