今日係你假期最後一日，你決定買啲紀念品，令自己記住呢段美好時光。有 $n$ 個商人，你喺每個商人嗰度都睇中一件貨品。第 $i$ 個商人嗰件貨品旁邊標住嘅價錢係 $c_i$。你帶咗 $S$ 蚊，準備全部用嚟買紀念品。你冇特別偏好，只想買盡可能多件唔同貨品。呢件事本來好簡單，但我哋講緊嘅係旅遊商店，佢哋靠容易上當嘅遊客發財。

第 $i$ 個商人有一個說服參數 $p_i$，唔同商人嘅參數唔同。你手上紀念品越多，商人就越肯定你願意花錢買冇用嘅垃圾。如果商人見到你已經買咗 $k$ 件紀念品，佢就會將自己嗰件紀念品加價至 $c_i+k\cdot p_i$。

你最多可以買幾多件紀念品？

輸入

第一行包含兩個整數 $n$ 同 $S$（$1\le n\le10^5$，$0\le S\le10^9$），分別表示商人數目同你有幾多錢。

第二行包含 $n$ 個整數 $c_1,c_2,\ldots,c_n$（$1\le c_i\le10^9$），表示所有紀念品嘅初始價錢。

第三行包含 $n$ 個整數 $p_1,p_2,\ldots,p_n$（$0\le p_i\le10^9$），表示所有商人嘅說服參數。保證佢哋互不相同。

輸出

輸出一個數，表示你可以買幾多件紀念品。

樣例

輸入 1

2 5
1 1
10 11

輸出 1

1

輸入 2

2 22
10 1
0 10000

輸出 2

2

輸入 3

1 0
1
0

輸出 3

0