思路

动态规划，三维dp，$dp[i][j][0]$ 代表在考虑前 $i$ 个商品的基础上，总共花费了 $j$ 元时能得到的最大的喜爱度，$dp[i][j][1]$ 代表相同条件的基础上第 $i$ 个商品用原价购买时的最大喜爱度。

$dp[i][j][0] = max(dp[i-1][j-a[i]][0] + b[i], dp[i-1][j-a[i]][1] + b[i])$

$dp[i][j][1] = max(dp[i][j][0], dp[i-1][j-a[i]/2][0] + b[i], dp[i-1][j][1])$

在dp更新过程中得到最大值即可

题目内容

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

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

小红有一定的存款，但是他想尽可能多地购买他喜欢的商品，因此他想知道在限制总价不超过 $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

样例解释

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