Description

The flower field is an $n \times n$ square. Each flower has its own label. $f_{i,j}$ represents the label in row $i$, column $j$.

The grasshopper is currently at row $r$, column $c$.

The grasshopper decides to explore a new world, so it wants to jump onto as many flowers as possible while following the rules below.

To jump from $(r_1, c_1)$ to $(r_2, c_2)$, it must satisfy one of the following conditions:

• $|r_1 - r_2| = 1$ and $|c_1 - c_2| > 1$,
• $|c_1 - c_2| = 1$ and $|r_1 - r_2| > 1$,

and also $f_{r_2, c_2} > f_{r_1, c_1}$.

Compute the maximum number of flowers the grasshopper can visit.

Input Format

The first line contains a single integer $n$.

The second line contains two integers $r$ and $c$.

The next $n$ lines each contain $n$ integers, representing the array $f$.

Output Format

Output one integer, the maximum number of flowers the grasshopper can visit.

4
1 1
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7 

4

5
3 3
20 16 25 17 12
11 13 13 30 17
15 29 10 26 11
27 19 14 24 22
23 21 28 18 13 

21

Hint

Constraints

• For $50\%$ of the testdata, $n \le 100$.
• For $80\%$ of the testdata, $n \le 10^3$.
• For $100\%$ of the testdata, $1 \le n \le 1.5 \times 10^3$, $1 \le r, c \le n$, $1 \le f_{i,j} \le 10^6$.

Notes

This problem is translated from T5 SKAKAVAC of Croatian Open Competition in Informatics 2008/2009 Contest #1.

Translated by ChatGPT 5