Đề bài

Một khu vườn có n cây tiên. Cây thứ i đứng ở tọa độ i, có giá trị là A_i và độ tiên là h_i.

Bạn trong vai một tên trộm tài ba, muốn hái trộm càng nhiều cây tiên càng tốt (chỉ quan tâm số lượng, không quan tâm tổng giá trị lớn hay nhỏ). Tuy nhiên, có một số ràng buộc:

Chỉ được phép trộm các cây liên tiếp nhau.

Giả sử bạn trộm k cây tiên có độ tiên lần lượt là h_i, h_i+1, …, h_i+k-1 thì cần đảm bảo:

h_j chia hết cho h_j+1 với mọi i ≤ j < i+k-1.

Tổng giá trị các cây trộm được (tổng các A_i) phải không vượt quá m.

Yêu cầu: Tìm số lượng cây tối đa có thể trộm được.

Input

Dòng đầu tiên chứa hai số nguyên dương n, m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁹).

Dòng thứ hai chứa n số nguyên dương A_i (1 ≤ A_i ≤ 10⁴) — giá trị của cây thứ i.

Dòng thứ ba chứa n số nguyên dương h_i (1 ≤ h_i ≤ 10⁴) — độ tiên của cây thứ i.

Output In ra một số nguyên duy nhất — số lượng cây tối đa có thể trộm được.

Example

Input

5 12
3 2 4 1 8
4 4 2 4 1

Output

3