Vending Machine

A snack vending machine sells $n$ kinds of snacks, numbered $1$ through $n$. A snack of kind $i$ has price $c_i$, and the machine currently holds $l_i$ snacks of that kind.

The machine is broken. When you buy a snack of kind $i$ (which is allowed only while at least one snack of kind $i$ is still in stock), the machine charges you $c_i$ and then dispenses that snack together with one snack of every kind $1, 2, \ldots, i-1$ that still has stock. Kinds among $1, \ldots, i-1$ that are already sold out are simply skipped. Every dispensed snack (the one you paid for and each bonus one) reduces that kind's remaining stock by one.

Starting with $k$ units of money, you may keep buying snacks in any order, and you do not have to spend all of your money. Determine the maximum possible total value — the sum of the prices $c_i$ of all snacks you receive, both purchased and bonus — that you can collect without your spending exceeding $k$.

The first line contains two integers $n$ and $k$ $(1 \le n \le 40,\ 1 \le k \le 64000)$ — the number of snack kinds and the amount of money available.

The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ $(1 \le c_i \le 40)$ — the prices of the snack kinds.

The third line contains $n$ integers $l_1, l_2, \ldots, l_n$ $(0 \le l_i \le 40)$ — how many snacks of each kind the machine currently holds.

Print a single integer: the maximum total value of snacks obtainable while spending at most $k$ units of money.

In the first example, buy a snack of kind $6$ (paying $c_6 = 2$): the machine also releases one snack of kinds $1, 2, 4$ and $5$ (kind $3$ is out of stock and is skipped). Then buy a snack of kind $4$ (paying $c_4 = 5$): it additionally releases one snack of kind $2$. The two purchases cost $2 + 5 = 7 \le 8$ and yield snacks worth $30$ in total.