21090번 - Trade 다국어

문제

It is the last day of your vacation and you decided to buy some memorabilia to remind you about these nice times. There are $n$ merchants, you liked one item from each one. The price written beside the item from $i$-th merchant is $c_{i}$. You have $S$ money with you, and you are ready to spend them on the souvenirs. You don't have any preference so you just want to buy as many different items as possible. It would be an easy job but this is tourist shops we are talking about. They thrive on gullible tourists.

$i$-th merchant has a persuasion parameter $p_{i}$ and they are different for different merchants. The more souvenirs you already have, the more a merchant is sure about your willingness to spend money on worthless crap. If a merchant sees that you have already bought $k$ souvenirs, he raises the price on his souvenir to $c_{i} + k \cdot p_{i}$.

What is the maximal number of souvenirs you can buy?

입력

The first line contains two integers $n$ and $S$ (1ドル \le n \le 10^{5},ドル 0ドル \le S \le 10^{9}$) --- the number of merchants and the amount of money you have.

The second line contains initial prices of all the souvenirs $c_{1}, c_{2}, \ldots, c_{n}$ (1ドル \le c_{i} \le 10^{9}$).

The third line contains persuasion parameters of all the merchants $p_{1}, p_{2}, \ldots, p_{n}$ (0ドル \le p_{i} \le 10^{9}$). It is guaranteed that they are distinct.

출력

Print one number --- how many souvenirs you can buy.

제한

힌트