Jobstown Millionaire

Task

In Jobstown, where time and payments are intertwined, a skilled worker named Alex is trying to put together a nest egg.
Alex found out that there are $N$ jobs available in the city, each with a completion time $T_i$ and a corresponding payment $P_i$ (in byte-dollars).

Alex has to select some jobs to do, with the freedom to perform the same job multiple times: note that he can only work for one job at any given moment (but after finishing a job, he can start working on a new one immediately), and he receives the payment for the job only after finishing it completely (half-finished work is not tolerated in Jobstown!).

Alex occasionally finds himself working for too many days straight, though: this time, he decided to place a limit on the amount of work he will do, namely no more than $M$ total time of work will be done by him.

Find the maximum amount of money Alex can make by choosing the jobs in the best way!

Input data

The first line contains $N$ and $M$, the number of jobs and the limit on the total time Alex spends on doing jobs.

The second line contains $N$ integers $T_i$, the completion times.

The third line contains $N$ integers $P_i$, the payments received for completed jobs.

Output data

You need to write a single line with an integer: the maximum amount of money Alex can make.

Constraints and clarifications

• $1 \le N \le 500$.
• $1 \le M \le 10^9$.
• $1 \le T_i \le 500$ for each $i=0\ldots N-1$.
• $1 \le P_i \le 10^9$ for each $i=0\ldots N-1$.
• A nest egg is a sum of money saved or invested for a specific purpose, often for retirement or a major purchase.

Example 1

stdin

3 10
3 2 4
1 4 9

stdout

22

Explanation

In the first sample case, Alex has to do the third job twice and the second job once. This way, he makes $2 \cdot 9 + 1 \cdot 4 = 22$ byte-dollars.

Example 2

stdin

4 23
4 5 6 8
7 9 11 16

stdout

43

Explanation

In the second sample case, Alex can maximize his earnings by doing each job exactly once.
Another possibility is to do the third job once and the fourth job twice. Note that the latter schedule takes less time to complete, but yields the same profit.