Hamming

Khoảng cách Hamming giữa hai xâu là số vị trí mà tại đó, kí tự ở hai xâu là khác nhau; trong lưu trữ và xử lí thông tin, người ta cũng đưa ra định nghĩa tương tự cho các số nhị phân: Khoảng cách Hamming giữa hai số nhị phân là số vị trí mà tại đó, trạng thái của hai bit ở hai số là khác nhau.

Cho hai dãy số nguyên không âm có cùng kích thước \(n\) : \(a_{1},a_{2},...,a_{n}\) và \(k_{1}, k_{2}, ..., k_{n}\) . Một dãy số \(i_{1}, i_{2},...,i_{k}\) gọi là đẹp nếu:

• \(1 \leq i_{1} < i_{2} < ... < i_{k} \leq n\)
• Khoảng cách Hamming giữa \(a_{i_{j}}\) và \(a_{i_{j−1}}\) đúng bằng \(k_{i_{j}}\) với mọi \(j\): $ 2 \leq j \leq k$

Hiện tại Quân đang thấy khó khăn khi phải tìm dãy số đẹp có kích thước lớn nhất.

Yêu cầu: Bạn hãy giúp Quân tìm dãy số đẹp có kích thước lớn nhất nhé.

Input

Dòng đầu tiên chứa số nguyên dương \(n\) \((n \leq 10^5)\)

Dòng thứ hai chứa \(n\) số nguyên \(a_{1},a_{2},...,a_{n}\) \((0 \leq a_{i} \leq 10^6)\)

Dòng thứ ba chứa n số nguyên \(k_{1}, k_{2}, ..., k_{n}\) \((0 \leq k_{i} \leq 10^6)\)

Output

In ra một số nguyên duy nhất là kích thước của dãy số đẹp tìm được.

Example

4
1 2 3 4
10 0 1 0

2

2
8 9
20 0

1

5
5 3 5 3 5
10 1 20 1 20

1

Scoring

Có \(20\%\) số điểm với \(n \leq 15\)

Có \(25\%\) số điểm với \(n \leq 5000\)

Có \(25\%\) số điểm với \(a_{1},a_{2},...,a_{n} \leq 1000\)

Còn lại không có điều kiện gì thêm