ПДД в ЛКШ
Совсем недавно девятиклассник Коля прибыл в Летнюю Кинематографическую Школу.
Первым делом он решил посетить киностудию. В детском лагере "Орлёнок", где ЛКШ проводилось в том году, проложено множество асфальтированных дорожек и их пересечения образуют перекрёстки. "Орлёнок" - необычный лагерь, и поэтому на всех дорожках и перекрёстках нарисован разметка, а также действуют правила дорожного движения, за нарушение которых полагаются штрафы.
Киностудия расположена на юго-востоке от корпуса, в котором живёт Коля, поэтому школьник решил передвигаться только на восток и на юг. Ему очень хотелось побыстрее добраться до киностудии, и потому он решил не обращать внимания на правила, и переходить перекрёстки как ему вздумается. Однако, как настоящий ЛКШонок, Коля должен был позаботится о том, чтобы суммарный размер штрафов за его нарушения был минимален. Помогите ему в этом.
В вашем распоряжении карта лагеря, представляющая собой клетчатый прямоугольник N на M, в котром на пересечинии i-й строки и j-ого столбца указан размер штрафа при попадании на этот перекрёсток.
Корпус, в котором живёт Коля, находится в северо-западном углу лагеря, а киностудия - в юго-восточном. Помогите Коле добраться до места назначения, заплатив минимально возможный штраф.
Входные данные
В первой строке входного файла находятся два натуральных числа N и M (1 ≤ N, M ≤ 1000).
В последующих N строках находятся по M чисел - карта лагеря "Орлёнок".
Выходные данные
В первой строке выведите одно целое число - минимальный размер штрафа, который придётся заплатить Коле. Во второй строчке выведите количество перекрёстков на пути. В следующих строчках выведите координаты перекрёстков, через которые школьник пройдёт. Гарантируется, что штраф не превысит 10^9.