#C05L12P06. C05.L12.二维前缀和.课后附加题1.奶牛产奶

C05.L12.二维前缀和.课后附加题1.奶牛产奶

题目描述

Bessie 坚信在她最喜爱的农场中存在着一小块世界上最美妙的草地. 她认为找出这块草地对奶牛产奶有帮助。

每只牛都回到了各自安排的地方,她们所居住的地方恰好构成一个矩形. 像左下方的例子,行数 NR 为 6 ,列数 NC 为 5 。

Bessie 实际上已经知道每一只牛的产奶量 PrcP_{rc} ( 1 <= PrcP_{rc} <= 100 ); 每只牛的产奶量被表示为右下方的矩阵。

<th>1</th> <td>5</td> <td>6</td> <td>7</td> <td>4</td> <td>6</td> <th>6</th> <td>3</td> <td>4</td> <td>2</td> <td>3</td> <td>4</td>
1 2 3 4 5
2 7 7 8 6 5
3 9 9 8 3 5
4 8 8 7 6 4
5 4 5 2 4 5

Bessie 想要找出那块最美妙的草地. 她打算找出一块 3*3 的草地,使这块草地上的牛的产奶量最大。

如果有多块总和最大的草地,则输出行数较小的,如果行数也相同,就输出列数较小的。

输入格式

第 1 行: 两个用空格隔开的数字: NR 和 NC ( (3 <= NR , NC <= 100) )

第 2 至 NR+1 行: 每行包含 NC 个用空格隔开的整数,表示对应的奶牛的产奶量。

输出格式

第 1 行: 为找到的 3*3 草地上的产奶量

第 2 行: 为这块草地的左上角位置,有两个整数用一个空格隔开,第一个整数是这个草地的行坐标,第二个整数是这个草地的列坐标。

样例

6 5
5 6 7 4 6
7 7 8 6 5
9 9 8 3 5
8 8 7 6 4
4 5 2 4 5
3 4 2 3 4

71
2 1