Dãy đặc biệt

Cho hai dãy số nguyên cùng độ dài \(n\):
$
A=(a_1,a_2,\dots,a_n),\qquad B=(b_1,b_2,\dots,b_n),
$
và một số nguyên dương \(d\). Một dãy chỉ số \(i_1,i_2,\dots,i_k\) được gọi là đặc biệt nếu thỏa mãn:

• \(1 \le i_1 < i_2 < \dots < i_k \le n\);
• \(|a_{i_j}-a_{i_{j-1}}|\le d\) cho mọi \(j=2,\dots,k\);
• \(|b_{i_j}-b_{i_{j-1}}|\le d\) cho mọi \(j=2,\dots,k\).

Yêu cầu: Tìm một dãy chỉ số đặc biệt có số phần tử lớn nhất; in ra kích thước của dãy đó.

\InputFile

• Dòng đầu chứa hai số nguyên dương \(n,d\) (\(n \le 10^5\), \(d \le 10^9\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,\dots,a_n\) (với \(|a_i|\le 10^9\)).
• Dòng thứ ba chứa \(n\) số nguyên \(b_1,b_2,\dots,b_n\) (với \(|b_i|\le 10^9\)).

\OutputFile

• Ghi ra một số nguyên duy nhất --- kích thước của dãy chỉ số đặc biệt dài nhất.

\Scoring

• Có \(20\%\) số điểm với \(n \le 20\).
• Có \(20\%\) số điểm với \(n \le 2000\).
• Có \(20\%\) số điểm với \(n \le 30000\).
• Có \(20\%\) số điểm với \(b_1=b_2=\dots=b_n\).
• Phần còn lại không có ràng buộc gì thêm.

Example

5 3
1 2 3 4 5
5 1 4 3 2

4

10 187
110 -187 554 -722 811 -930 346 24 933 132
113 72 -962 77 -242 -118 256 -759 -756 368

1