Một trò chơi gồm có ~N~ màn chơi, các màn chơi được đánh số từ ~1~ đến ~N~, màn chơi thứ ~i~ có mã số ~a_i~ và chi phí là ~b_i~ ~(1 \le i \le N)~. Bạn chỉ được phép chọn một dãy liên tiếp các màn chơi từ vị trí ~l~ đến vị trí ~r~ thỏa mãn các điều kiện sau:

• Tại mỗi màn chơi thứ ~i~ ~(1 \le l \le i < r \le N)~, ~a_i~ luôn chia hết cho ~a_{i + 1}~.
• Tổng chi phí các màn chơi từ vị trí ~l~ đến vị trí ~r~ ~(b_i + b_{i + 1} + \ldots + b_r)~ không vượt quá số nguyên dương ~k~ cho trước.

Yêu cầu

Tìm cách chọn sao cho số lượng các màn chơi là nhiều nhất.

Dữ liệu đầu vào

Gồm ba dòng:

• Dòng thứ nhất ghi hai số nguyên dương ~N, k~ ~(2 \le N \le 2 \times 10^5;\ 1 \le k \le 10^9)~.
• Dòng thứ hai ghi ~N~ số nguyên dương ~a_1, a_2,..., a_N~ ~(1 \le a_i \le 10^9;\ 1 \le i \le N)~.
• Dòng thứ ba ghi ~N~ số nguyên dương ~b_1, b_2,..., b_N~ ~(1 \le b_i \le 10^5;\ 1 \le i \le N)~.

Các số trên cùng một dòng được ghi cách nhau một dấu cách.

Dữ liệu đầu ra

Gồm một số nguyên ~t~ duy nhất là số lượng màn chơi nhiều nhất mà bạn có thể chơi. Trường hợp không tìm được dãy màn chơi nào thỏa mãn thì ghi số ~0~.

Ràng buộc dữ liệu

• Có 60% số test ứng với 60% số điểm: ~N \le 10^3~.
• Có 40% số test ứng với 40% số điểm: không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

4 8
6 2 3 1
5 4 1 2

OUTPUT

2

Ví dụ 2

INPUT

4 8
6 2 3 2
5 4 1 2

OUTPUT

0