Bytecoin

One day, at the stroke of midnight, you suddenly find yourself transported $N$ days into the past. Unfortunately, you don't seem to recall much, but you do happen to remember the daily price movements of that one particular cryptocurreny, bytecoin. Naturally, you start planning out your strategy to make as much money as you can.

You start off with an initial capital of $C$ dollars. There are $N$ days on which you know the buy and sell prices of bytecoin. On day $i$, you can buy as many bytecoins as you like, for $b_i$ dollars each, and/or sell as many bytecoins as you like, for $s_i$ dollars each. As bytecoins cannot be divided, you can only trade them in integer amounts, and you can only sell a bytecoin if you own one.

What is the maximum amount of money you can have at the end of day $N$, if you buy and sell bytecoins optimally?

Input

The first line will contain two space-separated integers, $N$, the number of days, and $C$, your initial capital in dollars .

The second line will contain $N$ space-separated integers, $b_1, b_2, \dots, b_N$, the buy prices of bytecoin for each day.

The third line will contain $N$ space-separated integers, $s_1, s_2, \dots, s_N$, the sell prices of bytecoin for each day.

Output

You should output a single integer – the maximum number of dollars you can have at the end of day $N$.

This number is guaranteed to be no more than $1\,000\,000\,000$.

Constraints

• $2 \le N \le 50\,000$
• $1 \le C \le 100\,000$
• $1 \le s_i \le b_i \le 100\,000$ for all $i$

Subtasks

• Subtask 1 (20%): $N = 2$
• Subtask 2 (40%): $b_i = s_i$ for all $i$ – that is, the buy prices are the same as the sell prices on all days.
• Subtask 3 (40%): No further restrictions apply.

Sample Explanation

In the first sample case, you should pay $6 to buy two bytecoins on day 1, and then sell them for $8 on day 2, leaving you with $10.

In the second sample case, you should buy three bytecoins on day 1 and sell them all on day 2 for a profit of $9. This allows you to buy 4 bytecoins on day 3, which can be sold for $16 profit on day 4. In total this leaves you with $35.

In the third sample case, one optimal strategy is to buy three bytecoins on day 1 and then sell them all on day 4 for a profit of $15, leaving you with a total of $25.