휴가의 마지막 날, 당신은 즐거웠던 시간을 추억하기 위해 기념품을 사기로 했습니다. $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