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

Мутанты-2

Мутанты-2

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
3 4
5 9 4 3
3 1 6 9
8 6 8 12
Çıxış verilənləri #1
35
6
1 1
2 1
2 2
3 2
3 3
3 4