É o último dia das suas férias e decidiu comprar algumas recordações para se lembrar desses bons momentos. Há $n$ comerciantes e gostou de um artigo de cada um. O preço indicado junto do artigo do $i$-ésimo comerciante é $c_i$. Tem $S$ unidades de dinheiro consigo e está disposto a gastá-las em recordações. Como não tem preferências, quer apenas comprar o maior número possível de artigos diferentes. Seria uma tarefa fácil, mas estamos a falar de lojas para turistas. Elas prosperam à custa de turistas ingénuos.

O $i$-ésimo comerciante tem um parâmetro de persuasão $p_i$, e esses parâmetros são diferentes para comerciantes diferentes. Quanto mais recordações já tiver, mais convencido fica o comerciante da sua vontade de gastar dinheiro em tralha sem valor. Se um comerciante vir que já comprou $k$ recordações, aumenta o preço da sua para $c_i + k \cdot p_i$.

Qual é o número máximo de recordações que pode comprar?

Entrada

A primeira linha contém dois inteiros $n$ e $S$ ($1 \le n \le 10^5$, $0 \le S \le 10^9$), o número de comerciantes e a quantidade de dinheiro que tem.

A segunda linha contém $n$ inteiros $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le 10^9$), os preços iniciais de todas as recordações.

A terceira linha contém $n$ inteiros $p_1, p_2, \ldots, p_n$ ($0 \le p_i \le 10^9$), os parâmetros de persuasão de todos os comerciantes. É garantido que são distintos.

Saída

Imprima um número: quantas recordações pode comprar.

Exemplos

Entrada 1

2 5
1 1
10 11

Saída 1

1

Entrada 2

2 22
10 1
0 10000

Saída 2

2

Entrada 3

1 0
1
0

Saída 3

0