Мутанти-2#3739
Як Ви пам'ятаєте, в Інституті Мистецтв, Мутантів та Інформаційних Технологій розводять милих різнокольорових звіряток. Але раптом одне із звіряток знайшло вихід з Інституту і втікло. З волі долі воно потрапило у дивовижне місто Мутантоград. Ви не повірите, місто розбите на вулиці, на перетині вулиць знаходяться перехрестя.
Дивний ж Мутантоград тим, що ходити можна з перехрестя на перехрестя тільки на схід чи на південь, а також на кожному перехресті беруть штраф. Наш мутант знайшов карту міста, вона являє собою клітчатий прямокутник на , у якому на перетині -ого рядка та -го стовбця вказано розмір штрафу при попаданні на це перехрестя.
Тваринка знаходиться на північно-західному куті міста. Допоможіть їй дійти до південно-східного кута Мутантограда, заплативши мінімально можливий штраф.
У першому рядку вхідного файлу знаходиться два натуральних числа та (1 \leq N, M \leq 1000).
У наступних рядках міститься по чисел - карта міста Мутантограда.
У першому рядку виведіть одне ціле число — мінімальний розмір штрафу, який прийдеться заплатити мутанту.
У другому рядку виведіть кількість перехресть на шляху.
У наступних рядках виведіть координати перехресть, через які тваринка пройде. Гарантується, що штраф не перевищить 10^9.
Приклад 1