Bessie верит, что в любимом пастбище есть лучшая в мире особая трава, увеличивающая молоко.
Коровы вернулись на назначенные места полностью заполненной прямоугольной сетки. Слева $NR$ строк ($3 \le NR \le 100$),6, $NC$ столбцов ($3 \le NC \le 100$),5; коровы 'C'.
Знает молоко каждой $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$ с максимальной суммой9 значений и левый верхний угол, сначала строка, потом столбец. Справа максимум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