Bạn chơi một trò chơi có \(n\) màn chơi, trong đó màn chơi thứ \(i\) có giá trị là \(a_{i}\) và điểm nhận được là \(b_{i}\).

Bạn muốn chọn một dãy \textbf{liên tiếp} các màn chơi từ \(l\) đến \(r\) sao cho với mọi \(l \leq i < r\), \(a_{i}\) luôn chia hết cho \(a_{i + 1}\). Nếu bạn chọn dãy các màn chơi từ \(l\) đến \(r\), số điểm bạn nhận được là \(b_{l} + b_{l + 1} + \ldots + b_{r}\). Tuy nhiên, do giới hạn của trò chơi, số điểm bạn nhận được không được phép vượt quá \(k\) (có nghĩa là nếu tổng điểm bạn nhận được bạn vượt quá \(k\) thì xem như thua cuộc).

Do muốn tận hưởng trò chơi lâu nhất có thể, bạn muốn tìm dãy liên tiếp gồm nhiều màn chơi nhất. Hỏi trò chơi của bạn có thể diễn ra trong bao nhiêu màn?

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n,k\) \((1 \leq n \leq 2 \times 10^{5}, 1 \leq k \leq 10^{9})\).
• Dòng thứ hai chứa \(n\) số nguyên \(b_{1}, b_{2}, \ldots, b_{n}\) \((1 \leq b_i \leq 10^{5})\).
• Dòng thứ ba chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\).

Output

• Gồm một dòng chứa một số nguyên duy nhất là dãy dài nhất thỏa mãn, hoặc đưa ra số \(0\) nếu không có dãy nào thỏa mãn.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \leq 10^{3}\).
• Subtask \(2\) (\(25\%\) số điểm): \(b_{1} + b_{2} + \ldots + b_{n} \leq k\).
• Subtask \(3\) (\(25\%\) số điểm): \(a_{1} = a_{2} = \ldots = a_{n}\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

4 8
5 4 1 2
6 2 3 1

2