using System;
using System.IO;

namespace Джонсон
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string Path = "test.txt";
            string Path1 = "test1.txt";
            int n = 0;
            
            using (StreamReader sr = new StreamReader(Path))
            {
                string str = sr.ReadLine();
                while (str != null)
                {
                    n++; 
                    str = sr.ReadLine();
                    
                }

            }
            int[,]mass = new int[n, 2];
            int l = 0;
            using (StreamReader sr = new StreamReader(Path))
            {
                string str = sr.ReadLine();
                while (str != null)
                {
                    string[] strs = new string[2];                  
                    strs = str.Split(" ").ToArray();
                    mass[l,0] = Convert.ToInt32(strs[0]);
                    mass[l, 1] = Convert.ToInt32(strs[1]);
                    l++;
                    str = sr.ReadLine();
                }

            }
            for(int i  = 0; i < n; i++)
            {
                for(int j = 0;j < 2; j++)
                {
                    Console.Write(mass[i,j] + " ");
                }
                Console.WriteLine();
            }

            Console.WriteLine("Максимум для исходного: " + max(n, mass));
            int rez = max(n, mass);
            Console.WriteLine();
            int k = 0;
            int b = n; 
            int ii = 0;
            int ij = 0;
            int[,] mass1 = new int[n, 2];
            while (b-k !=0)
            {
                int min = 9999;
                int min1 = 0;
               
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < 2; j++)
                    {
                        if (mass[i, j] <= min && mass[i, j]!=0)
                        {


                            if(mass[i, j] == min)
                            {
                                if(j == 0 && mass[i, 1] < min1)
                                {
                                    min = mass[i, j]; 
                                    ii = i;
                                    ij = j;
                                }
                                else if (j == 1 && mass[i, 0] < min1)
                                {
                                    min = mass[i, j];
                                    ii = i;
                                    ij = j;
                                }
                            }
                            if (mass[i, j] < min)
                            {
                                min = mass[i, j];
                                ii = i;
                                ij = j;
                            }
                            if (j == 0)
                            {
                                min1 = mass[i, 1];
                            }
                            else
                            {
                                min1 = mass[i, 0];
                            }
                           
                           
                        }
                    }
                }
                int flag = 0;
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < 2; j++)
                    {

                        if(i >= k && i <= b)
                        {

                            if (ij == 0)
                            {
                                mass1[k, 0] = min;
                                mass1[k, 1] = min1;
                                mass[ii, ij] = 0;
                                mass[ii, 1] = 0;
                            }
                            else if (ij == 1)
                            {
                                mass1[b-1, 1] = min;
                                mass1[b-1, 0] = min1;
                                mass[ii, ij] = 0;
                                mass[ii, 0] = 0;
                                flag = 1;
                            }



                        }





                        
                    }

                }
               
                if(flag == 1)
                {
                      b--;
                }
                else if(flag == 0)
                {
                     k++;
                }
               



                
            }
            Console.WriteLine("Оптимальная матрица: ");
            Console.WriteLine();
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < 2; j++)
                {
                    Console.Write(mass1[i, j] + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
            Console.WriteLine("Максимум для оптимального: " + max(n, mass1));
            using (StreamWriter sw = new StreamWriter(Path1, true))
            {
                sw.WriteLine();
                sw.WriteLine("Время простоя при исходном порядке: " + rez);
                sw.WriteLine("Оптимальная матрица:");
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < 2; j++)
                    {
                        sw.Write(mass1[i, j] + " ");
                    }
                    sw.WriteLine();
                }
                sw.WriteLine();
                sw.WriteLine("Время простоя при оптимальном порядке: "+ max(n, mass1));
            }
        }
        static int max(int n, int[,] mass)
        {
            int m = 0;
            int itog = 0;
            while (m <= n)
            {
                int max = 0;
                for (int i = 0; i < m; i++)
                {
                    max = max + mass[i, 0];
                }
                for (int i = 0; i < m - 1; i++)
                {
                    max = max - mass[i, 1];
                }
                if (max > itog)
                {
                    itog = max;
                }

                m++;
            }
            return itog;
        }
    }
}