D-游游买商品_牛客周赛 Round 18

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

游游正在逛超市，有 $n$ 个商品摆成一排，第 $i$ 个商品的价格为 $a_i$ ，游游对它的喜爱度为 $b_i$ 。所有商品的价格都是偶数。

超市开展了一个活动，当游游花费原价买了一件商品时，她可以用半价买下一件右边相邻的商品（也可以用原价购买，这样该商品右边的商品就有一次享受半价的机会）。但如果游游半价购买了一件商品，那么下一件右边相邻的商品只能原价购买。

换言之，如果游游想要半价买某一件商品，必须先用原价买下它相邻的左边的那个商品。

游游初始的钱为 $x$ ，她想要买的商品的喜爱度总和尽可能大，但总价格不能超过 $x$ 。你能帮帮她计算最大的喜爱度总和吗？

第一行输入两个正整数和，分别代表商品的数量，以及游游初始的金额数。
第二行输入个正整数，分别代表每个商品的价格。
第三行输入个正整数，分别代表每个商品可以给游游带来的喜爱度。


保证所有的都是偶数。

一个整数，代表最终喜爱度之和的最大值。

示例1

复制

4 7
2 2 6 2
3 4 5 1

复制

第一个使用原价买，第二个物品使用原价买，第三个物品使用半价买，不买第四个物品，这样是最优的。
请注意，如果第二个物品使用了半价，那么第三个物品则不能使用半价。

示例2

复制

3 3
4 10 6
3 2 4

复制

钱不够，无法购买任何物品。