e-olymp
Задачи

Черепашка: восстановление

Черепашка: восстановление

Черепашка хотела бы как можно быстрее пройти по прямоугольной таблице из левого верхнего угла в правый нижний по маршруту с наименьшими потерями.

Входные данные

В первой строке записаны два натуральных числа n и m, не превосходящих 1000 - размеры таблицы. Далее идёт n строк, каждая из которых содержит m чисел, разделённых пробелами - описание таблицы с указанием для каждой клетки таблицы содержания кислоты на ней (в миллилитрах).

Черепашка может ходить только вправо и вниз в соседние клетки.

Выходные данные

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

prb4019.gif

Лимит времени 2 секунды
Лимит использования памяти 128 MiB
Входные данные #1
3 4
5 9 4 3
3 1 6 9
8 6 8 12
Выходные данные #1
35
1 1
2 1
2 2
2 3
3 3
3 4
Входные данные #2
1 1
1
Выходные данные #2
1
1 1