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