using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp40
{
class Program
{
struct Pair
{
int first;
int second;
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
static void Main(string[] args)
{
int summa = 0;
//ввод данных
int n = int.Parse(Console.ReadLine());
int m = int.Parse(Console.ReadLine());
int[,] A = new int[n, m];
for (int k = 0; k < n; k++)
{
for (int h = 0; h < m; h++)
{
A[k, h] = int.Parse(Console.ReadLine());
}
}
//заполнение вспомогательного массива
int[,] solution = new int[n, m];
solution[0, 0] = A[0, 0];
for (int k = 1; k < m; k++)
{
solution[0, k] = A[0, k] + solution[0, k - 1];
}
for (int k = 1; k < n; k++)
{
solution[k, 0] = A[k, 0] + solution[k - 1, 0];
}
for (int k = 1; k < n; k++)
{
for (int h = 1; h < m; h++)
{
solution[k, h] = A[k, h] + Math.Min(solution[k - 1, h], solution[k, h - 1]);
summa++;
}
}
Console.WriteLine(solution[n - 1, m - 1]);
Console.WriteLine($"{summa}");
//восстановление пути
int i = n, j = m;
Stack<Pair> stack = new Stack<Pair>();
while((i != 0) && (j != 0))
{
if(solution[i ,j] - A[i,j] == solution[i - 1, j]) // здесь выходит за массив
{
stack.Push(new Pair(i - 1, j));
--i;
}
else
{
stack.Push(new Pair(i, j - 1));
--j;
}
Console.WriteLine(stack.Pop());
}
Console.ReadKey();
}
}
}