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

Вхідні дані

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

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

Вихідні дані

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

Приклади