eolymp
bolt
Try our new interface for solving problems
Məsələlər

ПДД в ЛКШ

ПДД в ЛКШ

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Совсем недавно девятиклассник Коля прибыл в Летнюю Кинематографическую Школу.

Первым делом он решил посетить киностудию. В детском лагере "Орлёнок", где ЛКШ проводилось в том году, проложено множество асфальтированных дорожек и их пересечения образуют перекрёстки. "Орлёнок" - необычный лагерь, и поэтому на всех дорожках и перекрёстках нарисован разметка, а также действуют правила дорожного движения, за нарушение которых полагаются штрафы.

Киностудия расположена на юго-востоке от корпуса, в котором живёт Коля, поэтому школьник решил передвигаться только на восток и на юг. Ему очень хотелось побыстрее добраться до киностудии, и потому он решил не обращать внимания на правила, и переходить перекрёстки как ему вздумается. Однако, как настоящий ЛКШонок, Коля должен был позаботится о том, чтобы суммарный размер штрафов за его нарушения был минимален. Помогите ему в этом.

В вашем распоряжении карта лагеря, представляющая собой клетчатый прямоугольник N на M, в котром на пересечинии i-й строки и j-ого столбца указан размер штрафа при попадании на этот перекрёсток.

Корпус, в котором живёт Коля, находится в северо-западном углу лагеря, а киностудия - в юго-восточном. Помогите Коле добраться до места назначения, заплатив минимально возможный штраф.

Giriş verilənləri

В первой строке входного файла находятся два натуральных числа N и M (1N, M1000).

В последующих N строках находятся по M чисел - карта лагеря "Орлёнок".

Çıxış verilənləri

В первой строке выведите одно целое число - минимальный размер штрафа, который придётся заплатить Коле. Во второй строчке выведите количество перекрёстков на пути. В следующих строчках выведите координаты перекрёстков, через которые школьник пройдёт. Гарантируется, что штраф не превысит 10^9.

Nümunə

Giriş verilənləri #1
2 2
163 165
83 105
Çıxış verilənləri #1
351
3
1 1
2 1
2 2