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

در یک جدول $n$ در $n$، روی هر خانه یک عدد نوشته شده. خانه‌ی $(r, c)$ می‌خواهیم شروع کنیم و در جدول حرکت کنیم و در مسیر حرکت از بیشترین تعداد خانه‌ی ممکن عبور کنیم (یمررر)، با رعایت کردن این شرایط:

1. در مسیر حرکت، عدد نوشته شده روی هر خانه باید اکیداً کمتر از عدد نوشته شده روی خانه‌ی بعدی آن باشد.

2. در هر حرکت به سطر یا ستون مجاور حرکت می‌کنیم و حداقل ۳ خانه جابجا شویم. به بیان ریاضی، اگر در یک حرکت از $(r, c)$ به $(r2, c2)$ رفتیم، باید یکی از شرایط زیر برقرار باشد:

3. $|r2 - r| = 1$ و $|c2 - c| > 1$

4. $|c2 - c| = 1$ و $|r2 - r| > 1$

ورودی

در خط اول ورودی عدد $n$ آمده است که اندازه‌ی جدول را نشان می‌دهد. در خط بعد $r$ و $c$ آمده است. در $n$ خط بعدی جدول آمده است.

$$2 \le n \le 2\ 000$$ $$0 \le a_{i, j} \le 10^9$$

خروجی

بیشترین تعداد خانه‌ای که می‌توان با رعایت شروط گفته شده از آن‌ها یمررر کرد (عبور کرد) را چاپ کنید.

زیرمسئله‎ها

مثال

ورودی نمونه

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

خروجی نمونه

3

مسیر مورد نظر به این شکل است: $$(2, 1) - (4, 2) - (3, 4)$$