Byteasar 在 Bytetown 大学学习计算机科学。他所在的院系有一台自动售货机，出售 $n$ 种零食，编号为 $1$ 到 $n$。不同种类的零食价格可能不同，因为它们的大小和口味各异。

最近，Byteasar 发现这台自动售货机坏了。如果购买一种类型为 $i$ 的零食，自动售货机会额外赠送每种类型为 $1, 2, \dots, i-1$ 的零食各一个（前提是这些类型的零食还有库存；如果类型 $1, \dots, i-1$ 中某些零食已经售罄，则不会赠送这些零食）。购买类型为 $i$ 的零食的前提是该类型至少还有一个库存。

Byteasar 决定利用他发现的这个故障。他想知道，在拥有给定金额的情况下，他能从自动售货机中获得零食的最大总价值（即价格之和）是多少。他不需要花掉所有的钱。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 40, 1 \le k \le 64000$)：零食的种类数和 Byteasar 手头的金额。第二行包含 $n$ 个整数 $c_1, \dots, c_n$ ($1 \le c_i \le 40$)，表示各类型零食的价格。第三行包含 $n$ 个整数 $l_1, \dots, l_n$ ($0 \le l_i \le 40$)，表示自动售货机中各类型零食的库存数量。

输出格式

输出仅一行，包含一个整数：Byteasar 使用不超过 $k$ 的金额所能获得零食的总价值。

样例

样例输入 1

6 8
7 2 3 5 7 2
1 3 0 3 2 1

样例输出 1

30

说明

Byteasar 购买了一个类型为 $6$ 的零食。自动售货机额外赠送了类型 $1, 2, 4, 5$ 和 $6$ 的零食各一个。接着，Byteasar 购买了一个类型为 $4$ 的零食。除了这个零食外，自动售货机还赠送了一个类型为 $2$ 的零食。