ПДР в ЛКШ#4052
Коля, учень дев'ятого класу, нещодавно долучився до Літньої кінематографічної школи й вирішив спершу відвідати знімальний майданчик. Школа проходить у дитячому таборі "Орлятко", на території якого прокладено багато асфальтованих доріжок, що перетинаються на перехрестях. Окрім цього, табір унікальний тим, що всі доріжки та перехрестя позначені, а також на них діють правила дорожнього руху й за порушення стягується штраф.
Знімальний майданчик знаходиться на південний схід від місця проживання Колі, тож він планує рухатися лише на схід і на південь. Прагнучи якнайшвидше дістатися мети, Коля вирішує не зважати на правила й перетинати перехрестя вільно. Проте, як сумлінний учень ЛКШ, він хоче мінімізувати загальну суму штрафів, сплачених за порушення. Вам потрібно допомогти Колі досягти цієї мети.
У вашому розпорядженні є карта табору у вигляді сітки розміром N \times M. На кожному перехресті у -му рядку та -му стовпці вказано розмір штрафу за його перетин. Усі індекси у сітці 1-індексовані (1 \leq i \leq N, 1 \leq j \leq M).
Місце проживання Колі розташовується у північно-західному куті табору, а знімальний майданчик — у південно-східному. Ваше завдання — знайти маршрут, який дозволить Колі дістатися майданчика з мінімальним сумарним штрафом.
У першому рядку містяться два натуральних числа і (1 \leq N, M \leq 1000) — кількість рядків і стовпців у сітці.
Далі йде рядків по чисел у кожному — штрафи для кожного перехрестя відповідного ряду табору "Орлятко".
У першому рядку виведіть одне ціле число — мінімальну суму штрафу, яку доведеться сплатити Колі. У другому рядку виведіть кількість перехресть у оптимальному маршруті. У наступних рядках виведіть координати перехресть, якими пройде Коля у порядку з початку до фінішу (N, M). Кожен рядок має містити два числа: і (1 \leq i \leq N, 1 \leq j \leq M) відповідного перехрестя.
Гарантовано, що загальна сума штрафів не перевищить 10^9.
Приклад 1