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