SW Skill Test

The SW skill test runs for $T$ minutes and has $N$ problems. You may submit source code at any moment while the test is running.

Solving problem $i$ at minute $t$ earns $M_i - t \times P_i$ points. Solving problem $i$ takes the contestant $R_i$ minutes.

The contestant works on one problem at a time and never pauses a problem once started. The contestant freely chooses which problems to solve and in what order, and may skip any problem. If the test starts at minute 0, the solved problems run back to back, and the moment the last one is solved cannot exceed minute $T$.

The final score is the sum of the points of the solved problems, and it is 0 when no problem is solved. Write a program that finds the largest score the contestant can get.

The first line contains $N$ and $T$. ($1 \le N \le 50$, $1 \le T \le 100\,000$)

The second line contains $M_1, M_2, \ldots, M_N$, the third line contains $P_1, P_2, \ldots, P_N$, and the fourth line contains $R_1, R_2, \ldots, R_N$, each separated by spaces. ($1 \le M_i, P_i, R_i \le 100\,000$)

Print the largest score the contestant can get on the first line.