Es ist der letzte Tag deines Urlaubs, und du hast beschlossen, Erinnerungsstücke zu kaufen, die dich an diese schöne Zeit erinnern sollen. Es gibt $n$ Händler, und bei jedem gefällt dir ein Gegenstand. Neben dem Gegenstand des $i$-ten Händlers steht der Preis $c_i$. Du hast $S$ Geldeinheiten bei dir und bist bereit, sie für Souvenirs auszugeben. Du hast keine besonderen Vorlieben und möchtest einfach möglichst viele verschiedene Gegenstände kaufen. Das wäre einfach, aber hier geht es um Touristenläden. Sie leben von leichtgläubigen Touristen.

Der $i$-te Händler hat einen Überzeugungsparameter $p_i$, und diese Parameter sind für verschiedene Händler unterschiedlich. Je mehr Souvenirs du bereits hast, desto sicherer ist sich ein Händler, dass du bereit bist, Geld für wertlosen Schrott auszugeben. Sieht ein Händler, dass du bereits $k$ Souvenirs gekauft hast, erhöht er den Preis seines Souvenirs auf $c_i+k\cdot p_i$.

Wie viele Souvenirs kannst du höchstens kaufen?

Eingabe

Die erste Zeile enthält zwei Ganzzahlen $n$ und $S$ ($1\le n\le10^5$, $0\le S\le10^9$): die Anzahl der Händler und den Geldbetrag, den du bei dir hast.

Die zweite Zeile enthält $n$ Ganzzahlen $c_1,c_2,\ldots,c_n$ ($1\le c_i\le10^9$): die ursprünglichen Preise aller Souvenirs.

Die dritte Zeile enthält $n$ Ganzzahlen $p_1,p_2,\ldots,p_n$ ($0\le p_i\le10^9$): die Überzeugungsparameter aller Händler. Es ist garantiert, dass sie verschieden sind.

Ausgabe

Gib eine Zahl aus: wie viele Souvenirs du kaufen kannst.

Beispiele

Eingabe 1

2 5
1 1
10 11

Ausgabe 1

1

Eingabe 2

2 22
10 1
0 10000

Ausgabe 2

2

Eingabe 3

1 0
1
0

Ausgabe 3

0