Ini adalah hari terakhir liburan Anda dan Anda memutuskan membeli beberapa kenang-kenangan untuk mengingat masa-masa menyenangkan ini. Ada $n$ pedagang, dan Anda menyukai satu barang dari masing-masing pedagang. Harga yang tertulis di samping barang pedagang ke-$i$ adalah $c_i$. Anda membawa uang sebanyak $S$, dan siap membelanjakannya untuk suvenir. Anda tidak memiliki preferensi apa pun, jadi hanya ingin membeli sebanyak mungkin barang yang berbeda. Seharusnya ini mudah, tetapi yang kita bicarakan adalah toko-toko wisata. Mereka hidup dari turis yang mudah diperdaya.

Pedagang ke-$i$ memiliki parameter persuasi $p_i$, dan nilainya berbeda untuk pedagang yang berbeda. Semakin banyak suvenir yang sudah Anda miliki, semakin yakin pedagang bahwa Anda bersedia membelanjakan uang untuk sampah tak berguna. Jika pedagang melihat Anda sudah membeli $k$ suvenir, ia menaikkan harga suvenirnya menjadi $c_i + k \cdot p_i$.

Berapa banyaknya maksimum suvenir yang dapat Anda beli?

Masukan

Baris pertama berisi dua bilangan bulat $n$ dan $S$ ($1 \le n \le 10^5$, $0 \le S \le 10^9$), yaitu banyaknya pedagang dan jumlah uang yang Anda miliki.

Baris kedua berisi $n$ bilangan bulat $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le 10^9$), yaitu harga awal semua suvenir.

Baris ketiga berisi $n$ bilangan bulat $p_1, p_2, \ldots, p_n$ ($0 \le p_i \le 10^9$), yaitu parameter persuasi semua pedagang. Dijamin bahwa nilainya berbeda satu sama lain.

Keluaran

Cetak satu bilangan, yaitu banyaknya suvenir yang dapat Anda beli.

Contoh

Masukan 1

2 5
1 1
10 11

Keluaran 1

1

Masukan 2

2 22
10 1
0 10000

Keluaran 2

2

Masukan 3

1 0
1
0

Keluaran 3

0