C'est le dernier jour de vos vacances et vous avez décidé d'acheter quelques souvenirs pour vous rappeler ces bons moments. Il y a $n$ marchands, et vous avez aimé un article chez chacun d'eux. Le prix indiqué à côté de l'article du $i$-ième marchand est $c_i$. Vous avez $S$ argent avec vous, et vous êtes prêt à le dépenser pour les souvenirs. Vous n'avez aucune préférence, vous voulez donc simplement acheter autant d'articles différents que possible. Ce serait une tâche facile, mais nous parlons ici de boutiques touristiques. Elles prospèrent grâce aux touristes crédules.

Le $i$-ième marchand possède un paramètre de persuasion $p_i$, et ces paramètres sont différents pour chaque marchand. Plus vous possédez déjà de souvenirs, plus un marchand est sûr de votre volonté de dépenser de l'argent pour des babioles sans valeur. Si un marchand voit que vous avez déjà acheté $k$ souvenirs, il augmente le prix de son souvenir à $c_i + k \cdot p_i$.

Quel est le nombre maximal de souvenirs que vous pouvez acheter ?

Entrée

La première ligne contient deux entiers $n$ et $S$ ($1 \le n \le 10^5$, $0 \le S \le 10^9$) — le nombre de marchands et la quantité d'argent dont vous disposez.

La deuxième ligne contient $n$ entiers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — les prix initiaux de tous les souvenirs.

La troisième ligne contient $n$ entiers $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$) — les paramètres de persuasion de tous les marchands. Il est garanti qu'ils sont distincts.

Sortie

Affichez un seul nombre — combien de souvenirs vous pouvez acheter.

Exemples

Entrée 1

2 5
1 1
10 11

Sortie 1

1

Entrée 2

2 22
10 1
0 10000

Sortie 2

2

Entrée 3

1 0
1
0

Sortie 3

0