Как Вы помните, в Интституте Искусств, Мутантов и Информационных Технологий разводят милых разноцветных зверюшек. Но вдруг одна из зверюшек нашла выход из Института и сбежала. По воле судьбы она попала в удивительный город Мутантоград. Вы не поверите, город разбит на улицы, на пересечении улиц находятся перекрёстки. Удивителен же Мутантоград тем, что ходить можно с перекрёстка на перекрёсток только на восток или на юг, а также на каждом перекрёстке берут штрафы. Наш мутант нашёл карту города, она представляет собой клетчатый прямоугольник \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}.