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

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

Вхідні дані

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

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

Вихідні дані

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

Приклади