Giải bài trực tuyến

Mirko đang sinh sống trong một khu rừng rộng lớn có rất nhiều cây cao và vẫn đang lớn lên từng ngày. Khu rừng có thể miêu tả như một bảng NxN ô, mà mỗi ô có chứa 1 cây.

            Mirko đã thu thập thông tin, và cô biết được độ cao của mỗi cây, cũng như mức độ tăng trưởng của nó. Cây tăng trưởng liên tục, có nghĩa là nếu mức độ tăng trưởng của một cây là 5 mét 1 năm, thì sau nửa năm nó sẽ tăng lên được 2.5 mét.

            Mirko cũng đo được chiều cao của tất cả các cây. Tại mội thời điểm nào đó, một số cây nào đó sẽ có chiều cao bằng nhau, và Mirko tò mò rằng, liệu tại một thời điểm nào đó, vùng liên thông gồm tất cả các cây tại thời điểm đó có chiều cao bằng nhau gồm nhiều nhất là bao nhiêu cây. Hai ô được gọi là kề nhau nếu chúng có chung cạnh. Một vùng liên thông là một vùng mà tất cả các ô có thể đi tới được nhau khi đi qua một số ô kề cạnh với chúng. 

Input

• Dòng đầu là số nguyên N (N ≤ 700)

N dòng sau, mỗi dòng gồm N số, số thứ j của hàng i là giá trị h[i][j] thể hiện chiều cao của câu ở ô (i, j) ( h[i][j] ≤ 10⁶)

N dòng sau, mỗi dòng gồm N số, số thứ j của hàng i là giá trị v[i][j] thể hiện mức độ tăng trưởng của cây ở ô (i, j) (v[i][j] ≤ 10⁶)

Output

Số nguyên duy nhất là kết quả của bài toán.

Example

Input:
3
1 2 3
3 2 2
5 2 1
3 2 1
1 2 1
1 2 3

Output:
7