eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Черепашка: відновлення

Черепашка: відновлення

Ліміт часу 2 секунди
Ліміт використання пам'яті 128 MiB

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

Вхідні дані

У першому рядку записано два натуральних числа n та m~(n, m \le 1000) — розміри таблиці. Далі йдуть n рядків, кожен з яких містить m чисел, відокремлених пропусками — опис таблиці з вказуванням для кожної клітинки таблиці вмісту кислоти на ній (у мілілітрах).

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

Вихідні дані

У першому рядку виведіть одне ціле число — мінімальну можливу шкоду для черепашки. У наступних рядках виведіть координати клітинок, по яким пролягає відповідний шлях. Координати слід виводити у тому порядку, у якому вони зустрічаються на шляху.

Приклад

Вхідні дані #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