Migrated from Lutece 2798 砍编剧

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

“亲爱的山雀，请将我的箭、我的花与我的爱，带给那孓然独行的旅人”

在过完乐土剧情后，忍无可忍的xwx无需再忍，带上刀片打算找这有什么心理创伤的编剧来一场线下battle。为了能对编剧造成有效的伤害，xwx准备了$n$个刀片，第$i$ ($i=1,2,.....,n$)个刀片对应的伤害值为$a_i$ ,而能对编剧造成的有效伤害为xwx携带的刀片的伤害值的总和。相应的，每个刀片拥有自己的重量，第$i$($i=1,2,.....,n$)个刀片的重量为$w_i$。那么问题来了，xwx只有一个承重为$m$的包，也就是说，她能携带的刀片的重量之和不能超过$m$。在合理选择了携带的刀片后，xwx能给编剧带来的最大有效伤害是多少？

Input

输入共三行： 第一行包含两个正整数 $n$($3\le n \le500$) 和 $m$($10\le m \le50000$)，分别表示xwx准备的刀片数目与xwx的包的承重。 第二行包含$n$个正整数：$a_1$,$a_2$,......,$a_n$($1\le a_i \le 2000$) ,表示每把刀的伤害值。 第二行包含$n$个正整数：$w_1$,$w_2$,......,$w_n$($1\le w_i \le 2000$) ,表示每把刀的重量。

Output

输出共一行：表示xwx能给编剧带来的最大有效伤害。

Samples

4 13
1 7 8 5
1 6 7 2

15

Resources

2022 UESTC ICPC Training for Dynamic Programming