Совсем недавно девятиклассник Коля прибыл в Летнюю Кинематографическую Школу. Первым делом он решил посетить киностудию. В детском лагере "Орлёнок", где ЛКШ проводилось в том году, проложено множество асфальтированных дорожек и их пересечения образуют перекрёстки. "Орлёнок" - необычный лагерь, и поэтому на всех дорожках и перекрёстках нарисован разметка, а также действуют правила дорожного движения, за нарушение которых полагаются штрафы. Киностудия расположена на юго-востоке от корпуса, в котором живёт Коля, поэтому школьник решил передвигаться только на восток и на юг. Ему очень хотелось побыстрее добраться до киностудии, и потому он решил не обращать внимания на правила, и переходить перекрёстки как ему вздумается. Однако, как настоящий ЛКШонок, Коля должен был позаботится о том, чтобы суммарный размер штрафов за его нарушения был минимален. Помогите ему в этом. В вашем распоряжении карта лагеря, представляющая собой клетчатый прямоугольник \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}.