Зовсімм нещодавно дев'ятикласник Коля прибув у Літню Кінематографічну Школу. Першим ділом він вирішив відвідати кіностудію. У дитячому таборі "Орлятко", де ЛКШ проводилась у тому році, прокладено безліч асфальтованих доріжок і їх перетини утворюють перехрестя. "Орлятко" - незвичайний табір, і тому на усіх доріжках і перехресях намальовано розмітку, а також діють правила дорожнього руху, за порушення яких наклдаються штрафи. Кіностудія розміщена на південний схід від корпуса, у якому живет Коля, тому школяр вирішив пересуватись лише на схід і на південь. Йому дуже хотілось пошвидше дістатись до кіностудії, і тому він вирішив не звертати уваги на правила, і переходити перехрестя як йому заманеться. Проте, як справжнє ЛКШеня, Коля повинен був потурбуватись про те, щоб сумарний розмір штрафів за його порушення був мінімальним. Допоможіть йому у цьому. У вашому розпорядженні карта табору, яка являє собою клітчатий прямокутник \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}.