Bessie 相信最爱的牧场有块特殊草,是世上最好、能让牛多产奶。
每牛回到分配的吃草点,组成完全填满的直角网格。下左例行数 $NR$($3 \le NR \le 100$)为6,列数 $NC$($3 \le NC \le 100$)为5,牛的位置标 'C'。
Bessie 知道各牛产奶量 $P_{rc}$($1 \le P_{rc} \le 100$),下右网格标出产量。
列 列
1 2 3 4 5 1 2 3 4 5
+-------------- +--------------
1| C C C C C 1| 5 6 7 4 6
行 2| C C C C C 行 2| 7 7 8 6 5
3| C C C C C 3| 9 9 8 3 5
4| C C C C C 4| 8 8 7 6 4
5| C C C C C 5| 4 5 2 4 5
6| C C C C C 6| 3 4 2 3 4她想找特殊草,寻找总产量最大的 $3 \times 3$ 牛网格。
找九项和最大的 $3 \times 3$ 网格,报告左上角位置,先行后列。上右例最大71,左上角第2行第1列。
两个 $3 \times 3$ 网格同和,选最小行号;同一行仍并列,选最小列号。
输入格式
- 第1行:两个空格分隔整数 $NR$、$NC$。
- 第 $2..NR+1$ 行:第 $r+1$ 行有 $NC$ 个空格分隔整数,表示牧场网格第 $r$ 行。
输出格式
- 第1行:一个整数,$3 \times 3$ 方块最大和。
- 第2行:两个空格分隔整数,最佳 $3 \times 3$ 网格左上角行号、列号。
样例
输入格式 1
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
输出格式 1
71 2 1
题目作者:Rob Kolstad, 2009