题目4--点(a,b)的保护塔

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

有一个矩形区域被划分为N行M列的网格,每个格子里有一定数量的资源并记录在矩阵val中,坐标(x,y)位置上资源量为val[x][y],其val中每个元素的值为0~9的整数,如果你在某个网格(a,b)上造一座保护塔,那么你可以占领K个网格中的资源,这K个格子分别是(a+dx[1],b+dy[1]),(a+dx[2],b+dy[2]),...,(a+dx[K],b+dy[K]),注意(a,b)这格本身可能未必会被占领。现在你能建造不超过2个塔,问最多能占领多少资源?一个网格被多个塔占领时其资源只计算一次。另外如果计算的位置(a+dx[i],b+dy[i])在网格外,则不贡献任何资源。

Input

 多组测试数据,第一行一个整数T,表示测试数据数量,1<=T<=5
每组测试数据有相同的结构构成:
每组数据第一行三个整数N,M,K,其中2 <= N,M <= 100,1 <= K <= 10。
之后会有N行,每行M个元素,表示val矩阵。每个元素为0~9,占一个字符,元素间没空格。
再接下来有K行,每行两个整数dx[i]与dy[i],其中-(N-1) <= dx[i] <= N-1,-(M-1) <= dy[i] <= (M-1)。

Output

 每组数据一行输出,即可占领的最大资源总量。

Sample Input

3
2 2 2
11
11
0 0
0 1
2 2 2
11
11
0 0
1 1
2 2 1
15
61
0 0

Sample Output

4
3
11

Hint

 

Source