Рабочее место участника

Джон решил построить пиццерию, в которой можно заказать пиццу с доставкой на дом. Пицца будет продаваться по фиксированной цене, и клиент не платит за доставку. Поэтому, если клиент живет слишком далеко от пиццерии, расходы Джона на доставку могут превысить потенциальную прибыль, заложенную в стоимость пиццы. Расходы на доставку зависят от расстояния между пиццерией и домом клиента и не зависят от количества заказанных пицц. Чем больше пицц заказывает клиент, тем больше прибыль Джона. Джон решил не обслуживать клиентов, для которых расходы на доставку превышают прибыль – они должны заказывать пиццу в другом месте. Перед строительством пиццерии Джон провел опрос и выяснил сколько пицц в день будут покупать в каждом доме. Используя эти данные, Джон хочет найти место для строительства пиццерии, в котором прибыль от продаж будет максимальна.

Карта города задана с помощью матрицы размером `N\ times\ M`. Соседними считаются ячейки с общей стороной. Ячейки матрицы с числом 0 соответствует дорогам, улицам. Можно построить киоск-пиццерию в любой ячейке с 0 и он не будет мешать проезду или проходу. Можно перемещаться из ячейки с 0 только в соседнюю ячейку с 0, и такое перемещение соответствует одной единице расстояния. В любую ячейку с 0 можно попасть, начав движение из любой ячейки с 0. Ячейки матрицы с положительными числами означают дома, в которых будут заказывать пиццу, и число равно количеству заказываемых пицц. У каждой ячейки с положительным числом есть хотя бы одна соседняя ячейка, содержащая число 0. Пицца должна быть доставлена до "двери дома" – в любую соседнюю с домом ячейку с 0. Ячейки с положительными числами не являются проходными. Кроме того, в матрице есть ячейки, содержащие число –1 и соответствующие домам, в которых не будут заказывать пиццу, или каким-то препятствиям для проезда.

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

Напишите программу, которая вычисляет максимальную прибыль Джона и расположение пиццерии, обеспечивающее такую прибыль.

В первой строке ввода содержатся два целых числа `N` и `M` (`2\ ≤\ N,\ M\ ≤\ 40`) – размеры карты города. Далее следует `N` строк, содержащих по `M` целых чисел в диапазоне от `-1` до 100, разделенных пробелами. Существует хотя бы одна ячейка с 0 и хотя бы одна ячейка с положительным числом.

Вывести в первой строке одно целое число – максимальную прибыль. Во второй строке вывести два целых числа, разделенных пробелом – номер строки и номер столбца ячейки, строительство пиццерии в которой обеспечивает рассчитанную максимальную прибыль. Если есть несколько вариантов для ячейки, обеспечивающие максимальную прибыль, то можно вывести любой из них.

3 5
4 0 5 0 10
0 0 2 0 3
6 0 0 0 0

21
2 4

Пояснение к примеру: Дома с 2 и 3 являются соседними с ячейкой с 0, выбранной для строительства пиццерии, поэтому расстояние от пиццерии до этих домов равно 0. До дверей домов с 5 и 10 расстояние равно 1. До дома с 6 расстояние равно 3, а до дома с 4 – 5. Прибыль Джона равна (5-1)+(10-1)+(2-0)+(3-0)+(6-3)=21. Дом с 4 в сумму не входит, так как разность 4-5 меньше 0.