eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Постройка склада

Постройка склада

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

На одной из карт размера M×N игроку дается герой, который может в одной из клеток карты построить склад, где он будет накапливать различные предметы, которые разбросаны по карте. За один ход герой может:

  • переместиться в одну из клеток, соседних по горизонтали или вертикали;

  • взять один предмет, если в клетке, где он сейчас находится, есть по крайней мере один предмет, и у него в инвентаре не было ничего (предметы настолько тяжелы, что герой может нести не более одного);

  • передать предмет, имеющийся в инвентаре, в склад, если герой находится в клетке, где был построен склад.

Коля хочет знать в каком месте карты следует строить склад, чтобы после его постройки требовалось бы минимальное число ходов на нахождение и складирование всех предметов, которые есть на карте.

Входные данные

В первой строке заданы целые числа M и N, определяющие размеры карты (1M, N1000). В последующих M строках записано по N целых чисел, определяющих количества предметов в соответствующих клетках карты. Все эти числа неотрицательные и не превосходят 1000.

Выходные данные

В первой строке выведите координаты (номер строки и столбца) клетки, в которой следует разместить склад, а во второй – количество ходов, которое потребуется после этого для того, чтобы собрать все предметы. Учтите, что если предмет лежит в той же клетке, где уже находится склад, все равно его следует поднять и переложить в склад.

Пример

Входные данные #1
4 4
0 0 1 0
0 1 0 1
0 0 1 0
0 0 0 0
Выходные данные #1
2 3
16
Автор Виталий Неспирный
Источник Зимняя школа, Харьков 2011, День 6