這是你度假的最後一天，你決定買些紀念品來回憶這段美好的時光。這裡有 $n$ 位商人，你喜歡每位商人的一件商品。第 $i$ 位商人商品的標價為 $c_i$。你身上有 $S$ 元，並且準備好將這些錢花在紀念品上。你沒有特別偏好，只想盡可能購買多種不同的商品。這本來是一件簡單的工作，但我們談論的是觀光商店，他們靠著容易受騙的遊客獲利。

第 $i$ 位商人有一個說服參數 $p_i$，且不同商人的參數皆不相同。你擁有的紀念品越多，商人就越確定你願意花錢買這些沒用的東西。如果商人看到你已經購買了 $k$ 個紀念品，他會將他的商品價格提高到 $c_i + k \cdot p_i$。

請問你最多可以購買多少個紀念品？

輸入格式

第一行包含兩個整數 $n$ 和 $S$ ($1 \le n \le 10^5$, $0 \le S \le 10^9$)，分別代表商人數量和你擁有的金額。

第二行包含 $n$ 個整數 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$)，代表所有紀念品的初始價格。

第三行包含 $n$ 個整數 $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^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