题目内容

塔子哥是一名工薪族，每个月工资刚刚够支付日常开支，因此他总是需要在超市购买实惠的商品。

有一天，他进入了一家超市，发现超市正在举行一场特殊活动。当塔子哥花费原价买了一件商品时，他可以用半价买下一件右边相邻的商品(也可以用原价购买，这样该商品右边的商品就有次享受半价的机会)。但如果塔子哥半价购买了一件商品，那么下一件右边相邻的商品只能原价购买。

塔子哥有一定的存款，但是他想尽可能多地购买他喜欢的商品，因此他想知道在限制总价不超过 $x$ 的情况下，他最多可以获得多少喜爱度。

超市中有 $n$ 个商品，每个商品的价格为偶数，第 $i$ 个商品的价格为 $a_i$ ，塔子哥对它的喜爱度为 $b_i$ 。

现在，他想要买的商品的喜爱度总和尽可能大，但总价格不能超过 $x$ 。你能帮帮他计算最大的喜爱度总和吗？

输入描述

第一行输入两个正整数 $n$ 和 $x$ ，分别代表商品的数量，以及塔子哥初始的金额数。

第二行输入 $n$ 个正整数 $a_i$ ，分别代表每个商品的价格。

第三行输入 $n$ 个正整数 $b_i$ ，分别代表每个商品可以给塔子哥带来的喜爱度。

$1\le n,x,a_i\le 1000$

$1\le b_i \le 10^9$ 保证所有的 $a_i$ 都是偶数。

输出描述

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

样例

样例一

输入

5 10
2 2 6 8 4
2 1 4 9 3

输出

13

样例二

输入

3 3
4 10 6
2 1 5

输出

0

样例解释

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