Sau khi trải qua khóa huấn luyện khắc nghiệt của Tiến sĩ Đá Orochimaru, Koruto dành những ngày dài trong căn phòng tối, vùi mình vào những bản nhạc trong album của HIEUTHUHAI, buitruonglinh,... để cố gắng quên đi người cũ. Tuy nhiên, như HIEUTHUHAI đã hát, "âm nhạc có thể sẽ làm em buồn hoặc có thể sẽ làm em vui, đó là dao hai lưỡi..." và mỗi bản nhạc đều mang trong mình một sức mạnh tâm linh kỳ lạ.

Cụ thể, mỗi bản nhạc thứ \(i\) có một mức độ gây thương nhớ là \(a_i\) và mang cảm xúc \(b_i\). Tiến sĩ Đá phát hiện ra rằng nỗi nhớ không biến mất mà nó tồn đọng trong tâm trí. Nếu Koruto nghe một playlist mà mức độ thương nhớ \(P\) và cảm xúc \(Q\) mà playlist đó mang lại có \(|Q - P|\) lớn hơn khả năng chịu đựng là \(S\), Koruto sẽ khóc trong đêm và mơ thấy người cũ...

Yêu cầu: Hãy giúp Tiến sĩ Đá Orochimaru thống kê xem có tổng cộng bao nhiêu playlist khiến Koruto phải mơ thấy người cũ, biết rằng các bài hát trong playlist đều lấy từ danh sách gốc và Koruto không bao giờ nghe chế độ trộn nhạc ngẫu nhiên.

Input

Gồm 3 dòng:

• Dòng đầu chứa hai số nguyên \(n\) và \(S\) \((1 \le n \le 10^5, 1 \le S \le 10^{14})\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) \((a_i \le |10^9|)\).
• Dòng thứ ba chứa \(n\) số nguyên \(b_i\) \((b_i \le |10^9|)\).

Output

Gồm một dòng duy nhất là tổng số lượng đoạn nhạc thỏa mãn.

Example

3 5
1 2 3
7 1 10

4

Scoring

• Subtask 1 (\(30\%\) điểm): \(n \le 100, S \le 10^{14}, 0\le a_i, b_i \le 10^5\).
• Subtask 2 (\(40\%\) điểm): \(n \le 5000, S \le 10^{14}, |a_i|, |b_i| \le 10^7\).
• Subtask 3 (\(30\%\) điểm): Không có ràng buộc gì thêm.