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