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

namespace Археологи_строители
{
    class Program
    {
        static void Main(string[] args)
        {
            //Объявляем и задаем переменные "M" и "N", а так же переменную для результата
            int M,N=new int();
            int MyResult = 0;

            Console.WriteLine("Ведите Текущее количество ступенек и Сколько их должно быть:");
            M = int.Parse(Console.ReadLine());
            N = int.Parse(Console.ReadLine());

            // Создаем массив для хранения данных о ступенях. M-Количество ступенек, Цифра - для колонок длины и высоты
            int[,] mass = new int[M,2];

            // Запись значений в массив
            for (int x = 0; x < M; x++){
                for (int y = 0; y < 2; y++){

                    if (y==0){  //Чисто для юзерфрендли отображения
                        Console.Write($"Введите значение Длины для ступеньки №{x + 1}= ");} else{
                        Console.Write($"Введите значение Высоты для ступеньки №{x + 1}= ");}
                    mass[x, y] = Convert.ToInt32(Console.ReadLine());}
                    Console.WriteLine();}

            /* Как оказалось, самый простой способ определить какую же ступеньку надо "поднимать"-
             * это вычислить площадь гипотетически "заполняемого" пространства над ступенькой и взять
             * наименьшее значение.
             * 
             * Итак, допустим если у нас 5 ступенек, то нам нам необходимо записать 4 значения
             * (в рамках лестницы) площади заполняемых ступенек.
             * 
             * Перемножаем Длину ступеньки N на высоту ступеньки N+1, M-1 раз и сохраняем в массив
             */
            int M2 = M; //Дублируем изначальное число ступенек для контроля цикла
            for (int z = 0; z <M2-N; z++)
            {
                int[] acreage = new int[M - 1];

                for (int x = 0; x < M - 1; x++)
                {
                    for (int y = 0; y < 2; y++)
                    {
                        acreage[x] = mass[x, 0] * mass[x + 1, 1];
                    }
                }
                /*
                 * И так у нас есть все значения гипотетически заполняемой ступеньки.
                 * Ищем минимальное значение площади 
                 */
                int minAcreage = acreage[0];
                for (int i = 0; i < M - 1; i++)
                {
                    if (minAcreage > acreage[i])
                    {
                        minAcreage = acreage[i];
                    }
                }

                MyResult = MyResult+minAcreage; //Плюсуем данное значение в переменную результата

                // У нас есть минимальная площадь. Найдем номер данной ступеньки
                int IndexAcreage = Array.IndexOf(acreage, minAcreage);

                //"Достроим нужную нам ступеньку и запишем обновленные данные во временный массив"
                int[,] tempMass = new int[M - 1, 2]; //Он на размер меньше, т.к. и "полных" ступенек у нас стало меньше


                for (int x = 0; x < M - 1; x++)
                {
                    for (int y = 0; y < 2; y++)
                    {

                        //Ступеньки до IndexAcreage мы просто переписываем во временный массив
                        if (x < IndexAcreage)
                        {
                            tempMass[x, y] = mass[x, y];
                        }

                        //2 ступеньки от IndexAcreage мы превращаем в одну (застраивая их блоками)
                        else if (x == IndexAcreage)
                        {
                            tempMass[x, y] = mass[x, y] + mass[x + 1, y];
                        }

                        /* и после IndexAcreage мы та же копируем, но со сдвигом вправо, т.к. полноценных 
                         * ступенек стало меньше
                         */
                        else if (x > IndexAcreage)
                        {
                            tempMass[x, y] = mass[x + 1, y];
                        }
                    }
                }

                M = M - 1; //Поскольку ступенек теперь меньше, то и их фактическое число необходимо уменьшить
                for (int x = 0; x < M + 1; x++)
                {
                    for (int y = 0; y < 2; y++)
                    {
                        mass[x, y] = 0;
                    }
                }


                //переписываем данные в основной массив и запускаем следющую интерацию цикла
                for (int x = 0; x < M; x++)
                {
                    for (int y = 0; y < 2; y++)
                    {
                        mass[x, y] = tempMass[x, y];
                    }
                }
            }
            Console.WriteLine($"Минимально необходимое число блоков: {MyResult}");
            Console.ReadKey(true);

        }
    }
}