• محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

Nima lives in a big enchanted forest where trees are very tall and grow really quickly (And sometimes talk!). That forest can be represented as an N×NN \times N matrix where each field contains exactly one tree. Nima is very fond of the trees in this forest. He spent years observing them and talking to them, and for each tree, he measured how much it grew in a year. The trees grow continuously. For example, if the tree grows 3 meters in a year, it will grow 1.5 meters in half a year.

Apart from trees, Nima likes mushrooms from the enchanted forest. Sometimes, he eats suspicious colorful mushrooms, starts talking to trees, and the trees ask him peculiar questions. Yesterday, this unfortunate thing happened and the trees asked what would be the size of the largest connected group of trees that have equal heights if the trees continue growing at the same speed they’re growing at that moment.

Nima quickly measured the current height of all the trees in the forest and asked you to answer his question.

Two trees are considered adjacent if their fields in the matrix share a common edge. Two trees are considered connected if there is a sequence of adjacent trees that leads from the first to the second. A group of trees is considered connected if every pair of trees in the group is connected.

ورودی

The first line of input contains the integer N. Each of the following NN lines contains NN integers. The ii-th line contains the integers hi,jh_{i, j}, the initial height of the tree located in the ii-th row and jj-th column.

After that, NN more lines follow, each containing NN integers. The ii-th line contains the integers vi,jv_{i,j}, the growth speed of the tree located in the ii-th row and jj-th column.

1N7001 \le N \le 7001vi,j,hi,j1061 \le v_{i, j}, h_{i, j} \le 10^6

Warning: The size of the input is very large, so it is recommended to use fast input methods (For example, use BufferedReader instead of Scanner in Java, or use scanf instead of cin in C++, or use PyPy instead of Python).

خروجی

The only line of output must contain a single integer - the answer of the problem.

مثال

ورودی نمونه ۱

3
1 2 3
3 2 2
5 2 1
3 2 1
1 2 1
1 2 3
Plain text

خروجی نمونه ۱

7
Plain text

ورودی نمونه ۲

2
3 1
3 3
2 5
2 5
Plain text

خروجی نمونه ۲

3
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.