Задачи
Мутанты-2
Мутанты-2
Как Вы помните, в Интституте Искусств, Мутантов и Информационных Технологий разводят милых разноцветных зверюшек. Но вдруг одна из зверюшек нашла выход из Института и сбежала. По воле судьбы она попала в удивительный город Мутантоград. Вы не поверите, город разбит на улицы, на пересечении улиц находятся перекрёстки.
Удивителен же Мутантоград тем, что ходить можно с перекрёстка на перекрёсток только на восток или на юг, а также на каждом перекрёстке берут штрафы. Наш мутант нашёл карту города, она представляет собой клетчатый прямоугольник \textbf{N} на \textbf{M}, в котором на пересечении \textbf{i}-ой строки и \textbf{j}-го столбца указан размер штрафа при попадании на этот перекрёсток.
Зверюшка находится на северо-западном углу города. Помогите ей дойти до юго-восточного угла Мутантограда, заплатив минимально возможный штраф.
\InputFile
В первой строке входного файла находится два натуральных числа \textbf{N} и \textbf{M} (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{1000}).
В последующих \textbf{N} строках содержится по \textbf{M} чисел - карта города Мутантограда.
\OutputFile
В первой строке выведите одно целое число - минимальный размер штрафа, который придётся заплатить мутантику.
Во второй строчке выведите количество перекрёстков на пути.
В следующих строчках выведите координаты перекрёстков, через которые зверюшка пройдёт. Гарантируется, что штраф не превысит \textbf{10^9}.
Входные данные #1
3 4 5 9 4 3 3 1 6 9 8 6 8 12
Выходные данные #1
35 6 1 1 2 1 2 2 3 2 3 3 3 4