测试数据来自 system/1586

背景

安徽省芜湖市集训队第二次选拔

COCI 2008/2009 Contest #1 - skakavac

Description:Unknown(Chinese Simplified)
Data:Official
Program:Official

描述

一只蚱蜢在花园里。这块土地包含n*n的花朵按n行n列排列。我们知道每朵花的花瓣数。这只蚱蜢的初始位置在r行c列。它的目标是在遵守以下规则的同时访问的花越多越好。

●它只可以跳到相邻的行或列，如果它跳到了相邻的行，它必须至少跳两列；如果它跳到了相邻的列，它必须至少跳两行。换句话说就是，它可以从花(r1,c1)跳到花(r2,c2)，如果：
(|r1-r2|==1 && |c1-c2|>1) || (|c1-c2|==1 && |r1-r2|>1)
●下一朵花的花瓣数必须严格大于当前花的花瓣数。

写一个程序，计算出蚱蜢可以访问的花的最多的数目。

格式

输入格式

第一行包括一个整数n(1<=n<=1500)，表示土地的大小。

第二行包括两个整数r(1<=r<=n)和c(1<=c<=n)，表示蚱蜢的初始位置。

下面n行，每行包括n个正整数，每个小于1,000,000，表示花的花瓣数。

输出格式

输出仅一行，为蚱蜢可以访问的最多的花的数目。

样例1

样例输入1

#1:
4
1 1
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

#2:
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 

样例输出1

#1:
4

#2:
21

限制

每个点4 seconds.

提示

50%的数据中，n最大为100。

80%的数据中，n最大为1000。

最大数据14MB。

来源

安徽省芜湖市集训队第二次选拔

COCI 2008/2009 Contest #1 - skakavac

Description:Unknown(Chinese Simplified)
Data:Official
Program:Official