ffff

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace лаба7._3 {
    internal class Program {
        public struct pair {
            public int a, b;
            public pair(int aa, int bb) {
                a = aa;
                b = bb;
            }
        }
        static void Main(string[] args) {
            int n, m;
            using (StreamReader sr = new StreamReader("input.txt")) {
                string[] lines = sr.ReadLine().Split(' ');
                n = int.Parse(lines[0]);
                m = int.Parse(lines[1]);

            }
            int[,] mass = ReadmatrixFromFile("input.txt");
            int[,] mass2 = new int[n, m];
            int[,] mass3 = new int[n, m];

            int[,] massMax = new int[n, m];
            int[,] massMin = new int[n, m];

            mass2[0, m - 1] = mass[0, m - 1]; //правый верхний угол
            mass3[0, m - 1] = mass[0, m - 1]; //правый верхний угол
            massMax[0, m - 1] = int.MinValue; //максимум среди верхних и правых клеток
            massMin[0, m - 1] = int.MaxValue; //минимум среди верхних и правых клеток

            pair[,] way = new pair[n, m]; //предыдущие клетки для максимума
            pair[,] way1 = new pair[n, m];//предыдущие клетки для минимума

            way[0, m - 1] = new pair(-1, -1); //предыдущие клетки для максимума
            way1[0, m - 1] = new pair(-1, -1);//предыдущие клетки для минимума

            for (int i = 0; i < m - 1; i++) {
                //present i+1, m - 1
                // past i, m-1
                //правая вертикаль

                if (massMax[i, m - 1] > mass2[i, m - 1]) {
                    massMax[i + 1, m - 1] = massMax[i, m - 1];
                    way[i + 1, m - 1] = way[i, m - 1];
                } else {
                    massMax[i + 1, m - 1] = mass2[i, m - 1];
                    way[i + 1, m - 1] = new pair(i, m - 1);
                }
                mass2[i + 1, m - 1] = mass[i + 1, m - 1] + massMax[i + 1, m - 1];


                if (massMin[i, m - 1] < mass3[i, m - 1]) {
                    massMin[i + 1, m - 1] = massMin[i, m - 1];
                    way1[i + 1, m - 1] = way1[i, m - 1];
                } else {
                    massMin[i + 1, m - 1] = mass3[i, m - 1];
                    way1[i + 1, m - 1] = new pair(i, m - 1);
                }
                mass3[i + 1, m - 1] = mass[i + 1, m - 1] + massMin[i + 1, m - 1];


            }
            //for (int i = 0; i < m; i++)
            //{
            //    Console.WriteLine(mass2[i, m-1]);
            //}

            for (int i = m - 1; i > 0; i--) {
                //present 0, i - 1
                //past 0, i
                //верхняя горизонталь

                if (massMax[0, i] > mass2[0, i]) {
                    massMax[0, i - 1] = massMax[0, i];
                    way[0, i - 1] = way[0, i];
                } else {
                    massMax[0, i - 1] = mass2[0, i];
                    way[0, i - 1] = new pair(0, i);
                }
                mass2[0, i - 1] = mass[0, i - 1] + massMax[0, i - 1];


                if (massMin[0, i] < mass3[0, i]) {
                    massMin[0, i - 1] = massMin[0, i];
                    way1[0, i - 1] = way1[0, i];
                } else {
                    massMin[0, i - 1] = mass3[0, i];
                    way1[0, i - 1] = new pair(0, i);
                }
                mass3[0, i - 1] = mass[0, i - 1] + massMin[0, i - 1];
            }
            //for (int i = m - 1; i >= 0; i--)
            //{
            //    Console.WriteLine(mass2[0,i]);
            //}
            for (int i = 1; i < m; i++) {
                for (int j = m - 2; j >= 0; j--) {
                    //present i,j
                    //past1 i-1, j
                    // past2 = i, j+1

                    if (massMax[i - 1, j] > mass2[i - 1, j]) {
                        massMax[i, j] = massMax[i - 1, j];
                        way[i, j] = way[i - 1, j];
                    } else {
                        massMax[i, j] = mass2[i - 1, j];
                        way[i, j] = new pair(i - 1, j);
                    }

                    if (Math.Max(massMax[i, j + 1], mass2[i, j + 1]) > massMax[i, j]) {
                        if (massMax[i, j + 1] > mass2[i, j + 1]) {
                            massMax[i, j] = massMax[i, j + 1];
                            way[i, j] = way[i, j + 1];
                        } else {
                            massMax[i, j] = mass2[i, j + 1];
                            way[i, j] = new pair(i, j + 1);
                        }
                    }

                    mass2[i, j] = mass[i, j] + massMax[i, j];


                    if (massMin[i - 1, j] < mass3[i - 1, j]) {
                        massMin[i, j] = massMin[i - 1, j];
                        way1[i, j] = way1[i - 1, j];
                    } else {
                        massMin[i, j] = mass3[i - 1, j];
                        way1[i, j] = new pair(i - 1, j);
                    }

                    if (Math.Min(massMin[i, j + 1], mass3[i, j + 1]) < massMin[i, j]) {
                        if (massMin[i, j + 1] < mass3[i, j + 1]) {
                            massMin[i, j] = massMin[i, j + 1];
                            way1[i, j] = way1[i, j + 1];
                        } else {
                            massMin[i, j] = mass3[i, j + 1];
                            way1[i, j] = new pair(i, j + 1);
                        }
                    }
                    mass3[i, j] = mass[i, j] + massMin[i, j];


                }

            }

            PrintMatrix(mass);
            Console.WriteLine();
            PrintMatrix(massMin);
            Console.WriteLine();
            PrintMatrix(mass2);


            //максимальная сумма
            List<int> otvetMax = new List<int>();
            pair cords = new pair( n - 1, 0 );
            while (cords.a != -1 && cords.b != -1) {
                otvetMax.Add(mass[cords.a, cords.b]);
                cords = way[cords.a, cords.b];
            }

            Console.WriteLine($"Максимальная сумма: {mass2[m - 1, 0]}");

            Console.WriteLine("Путь:");
            for (int i = otvetMax.Count - 1; i >= 0; i--)
                Console.Write($"{otvetMax[i]} ");


            //минимальная сумма
            List<int> otvetMin = new List<int>();
            cords = new pair(n - 1, 0);
            while (cords.a != -1 && cords.b != -1) {
                otvetMin.Add(mass[cords.a, cords.b]);
                cords = way1[cords.a, cords.b];
            }

            Console.WriteLine();
            Console.WriteLine($"Минимальная сумма: {mass3[m - 1, 0]}");

            Console.WriteLine("Путь:");
            for (int i = otvetMin.Count - 1; i >= 0; i--)
                Console.Write($"{otvetMin[i]} ");

            /*
                    int maxSumma = mass2[m - 1, 0];
            Console.WriteLine($"Максимальная сумма, набранная ладьей = {maxSumma}");
            for (int i = 1; i < m; i++) {
                for (int j = m - 2; j >= 0; j--) {
                    //Console.WriteLine(mass[i, j]);
                    mass2[i, j] = mass[i, j] + Math.Min(mass2[i - 1, j], mass2[i, j + 1]);

                    // Console.ReadKey();
                }

            }
            int minSumma = mass2[m - 1, 0];
            //PrintMatrix(mass2);
            Console.WriteLine($"Минимальная сумма, набранная ладьей = {minSumma}");
            */
            Console.ReadKey();
        }

        static int[,] ReadmatrixFromFile(string nameFile) {
            int n, m;
            int[,] Matrix;
            using (StreamReader sr = new StreamReader(nameFile)) {
                string[] lines = sr.ReadLine().Split(' ');
                n = int.Parse(lines[0]);
                m = int.Parse(lines[1]);
                Matrix = new int[n, m];
                for (int i = 0; i < n; i++) {
                    lines = sr.ReadLine().Split(' ');
                    for (int j = 0; j < m; j++) {
                        Matrix[i, j] = int.Parse(lines[j]);
                    }
                }
            }
            return Matrix;
        }
        static void PrintMatrix(int[,] a) {
            for (int i = 0; i < a.GetLength(0); i++) {
                for (int j = 0; j < a.GetLength(1); j++) {
                    Console.Write($"{a[i, j]}\t");
                }
                Console.WriteLine();
            }
        }
    }
}