Es el último día de tus vacaciones y has decidido comprar algunos recuerdos para rememorar estos buenos tiempos. Hay $n$ comerciantes, y te ha gustado un artículo de cada uno. El precio escrito junto al artículo del $i$-ésimo comerciante es $c_i$. Tienes $S$ dinero contigo y estás dispuesto a gastarlo en los recuerdos. No tienes ninguna preferencia, así que simplemente quieres comprar tantos artículos diferentes como sea posible. Sería una tarea fácil, pero estamos hablando de tiendas para turistas. Se aprovechan de los turistas crédulos.

El $i$-ésimo comerciante tiene un parámetro de persuasión $p_i$, y estos son diferentes para cada comerciante. Cuantos más recuerdos ya tengas, más seguro está un comerciante de tu disposición a gastar dinero en baratijas inútiles. Si un comerciante ve que ya has comprado $k$ recuerdos, aumenta el precio de su recuerdo a $c_i + k \cdot p_i$.

¿Cuál es el número máximo de recuerdos que puedes comprar?

Entrada

La primera línea contiene dos enteros $n$ y $S$ ($1 \le n \le 10^5$, $0 \le S \le 10^9$) — el número de comerciantes y la cantidad de dinero que tienes.

La segunda línea contiene $n$ enteros $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — los precios iniciales de todos los recuerdos.

La tercera línea contiene $n$ enteros $p_1, p_2, \dots, p_n$ ($0 \le p_i \le 10^9$) — los parámetros de persuasión de todos los comerciantes. Se garantiza que son distintos.

Salida

Imprime un número: cuántos recuerdos puedes comprar.

Ejemplos

Entrada 1

2 5
1 1
10 11

Salida 1

1

Entrada 2

2 22
10 1
0 10000

Salida 2

2

Entrada 3

1 0
1
0

Salida 3

0