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