eolymp
bolt
Try our new interface for solving problems
Problems

Construction of warehouse

Construction of warehouse

На одной из карт размера \textbf{M×N} игроку дается герой, который может в одной из клеток карты построить склад, где он будет накапливать различные предметы, которые разбросаны по карте. За один ход герой может: \begin{itemize} \item переместиться в одну из клеток, соседних по горизонтали или вертикали; \item взять один предмет, если в клетке, где он сейчас находится, есть по крайней мере один предмет, и у него в инвентаре не было ничего (предметы настолько тяжелы, что герой может нести не более одного); \item передать предмет, имеющийся в инвентаре, в склад, если герой находится в клетке, где был построен склад. \end{itemize} Коля хочет знать в каком месте карты следует строить склад, чтобы после его постройки требовалось бы минимальное число ходов на нахождение и складирование всех предметов, которые есть на карте. \InputFile В первой строке заданы целые числа \textbf{M} и \textbf{N}, определяющие размеры карты (\textbf{1} ≤ \textbf{M}, \textbf{N} ≤ \textbf{1000}). В последующих \textbf{M} строках записано по \textbf{N} целых чисел, определяющих количества предметов в соответствующих клетках карты. Все эти числа неотрицательные и не превосходят \textbf{1000}. \OutputFile В первой строке выведите координаты (номер строки и столбца) клетки, в которой следует разместить склад, а во второй -- количество ходов, которое потребуется после этого для того, чтобы собрать все предметы. Учтите, что если предмет лежит в той же клетке, где уже находится склад, все равно его следует поднять и переложить в склад.
Time limit 1 second
Memory limit 64 MiB
Input example #1
4 4
0 0 1 0
0 1 0 1
0 0 1 0
0 0 0 0
Output example #1
2 3
16
Author Vitaly Nespirny
Source Winter School, Kharkov, 2011, Day 6