Информатика

(А. Кабанов) Иван собирает альбом с коллекционными наклейками. Альбом содержит 30 страниц, на каждой странице 8 мест для наклеек. Иван решил проверить свою коллекцию и понять, скольких наклеек ему не хватает для заполнения всего альбома и на какой странице ему не хватает наибольшего количества наклеек.

Входные данные представлены в файле 26-77.txt следующим образом. В первой строке входного файла записано число N -- количество наклеек, которые собрал Иван (натуральное число, не превышающее 10 000). В следующих N строках записано по два числа: сначала номер страницы в альбоме (натуральное число от 1 до 30), затем номер наклейки на странице (натуральное число от 1 до 8). Запишите в ответе два числа: количество наклеек, которых не хватает Ивану для заполнения альбома, и номер страницы, на которой отсутствует наибольшее количество наклеек. Если таких страниц несколько выберите последнюю из них.

Пример входного файла:

10
1 1
1 2
1 3
1 4
1 6
1 6
1 8
2 4
3 1
3 3

При таких входных данных будем считать, что Ивана интересуют только страницы с 1 по 3.

На первой странице ему не хватает 2 наклеек; на второй странице не хватает 7 наклеек; на 3 странице не хватает 6 наклеек (всего 15 наклеек, больше всех не хватает на странице 2). Ответ: 15 2.

(А. Кабанов) На производстве станок с ЧПУ обрабатывал некоторый набор деталей. В каждый момент времени станок может обрабатывать только одну деталь. Каждая деталь изготавливалась в определённый промежуток времени с момента начала рабочего дня. Простоем считается временной участок, в течение которого не обрабатывается ни одна деталь. Инженер решил узнать, какова суммарная длительность простоев за день и какова длительность наибольшего простоя. Общая длительность рабочего дня L секунд.

Входные данные представлены в файле 26-76.txt следующим образом. В первой строке входного файла находятся два числа через пробел: число L -- общая длина рабочего дня (натуральное число, не превышающее 10⁹) и число N -- количество изготовленных деталей (натуральное число, не превышающее 10 000). В следующих N строках находится по два числа через пробел. Первое число -- время начало обработки от начала рабочего дня (натуральное число, не превышающее 10⁹). Второе число -- время окончания обработки (натуральное число, не превышающее 10⁹).

Запишите в ответе два числа: суммарную длительность простоев за день и длительность наибольшего простоя.

Пример входного файла:

1000 4
600 750
350 450
0 350
950 1000

При таких условиях имеется два простоя: 450--600; 750--950. Их суммарная длительность 350, наибольший имеет длину 200. Ответ: 350 200.

(А. Кабанов) Автомат фиксирует пассажиров некоторого автобуса по ходу рейса. У каждого пассажира фиксируется время входа и выхода с момента начала рейса. Необходимо узнать максимальное количество пассажиров, одновременно находящихся в автобусе, и общее время, когда в автобусе был хотя бы один пассажир. Временем входа и выхода в автобус пренебречь.

Входные данные представлены в файле 26-75.txt следующим образом. В первой строке входного файла находится число N -- общее количество пассажиров (натуральное число, не превышающее 10 000). В следующих N строках находится по два числа. Первое число -- время входа пассажира от начала рейса (натуральное число, не превышающее 1 000 000). Второе число - время выхода пассажира от начала рейса (натуральное число, не превышающее 1 000 000).

Запишите в ответе два числа: количество пассажиров, одновременно находящихся в автобусе и общее время, когда в автобусе был хотя бы один пассажир.

Пример входного файла:

7
10 40
50 130
70 130
75 90
120 170
140 170
150 180

В приведённом примере пассажиры были в временных отрезках 10-40 и 50-180. Максимальное количество пассажиров одновременно 3. Ответ: 3 160.

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 640 на 480 точек. При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 640) и номер позиции в строке (целое число от 1 до 480). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, -- тёмной.

Вам нужно определить наибольшую длину цепочки в одной строке, в которой светлые и тёмные точки чередуются. Группа начинается и заканчивается светлой точкой. Если таких строк несколько, укажите номер первой из подходящих строк.

Входные данные представлены в файле 26-73.txt следующим образом. В первой строке входного файла записано целое число N -- количество частиц, попавших на экран. В каждой из следующих N строк записаны по два числа, разделённые пробелом: номер строки и номер позиции в строке.

Запишите в ответе два числа: сначала количество светлых точек в самой длинной цепочке чередующихся точек, затем -- номер строки, в которой находится эта цепочка.

Пример входного файла:

7
1 2
2 3
3 6
2 5
1 4
2 5
2 3

При таких исходных данных имеется две цепочки чередующихся точек: в позициях 2, 3 и 4 строки 1, и в позициях 3, 4 и 5 строки 2. Обе они включают по 2 светлых точки, минимальный номер строки -- 1. Ответ: 2 1.

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 640 на 480 точек. При попадании очередной частицы на экран в файл записываются координаты чувствительного элемента: номер строки (целое число от 1 до 640) и номер позиции в строке (целое число от 1 до 480). Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, -- тёмной.

Вам нужно определить наибольшую длину цепочки в одной строке, состоящей только из светлых точек, и строку, в котором она находится. Если таких строк несколько, укажите максимальный из их номеров.

Входные данные представлены в файле 26-73.txt следующим образом. В первой строке входного файла записано целое число N -- количество частиц, попавших на экран. В каждой из следующих N строк записаны по два числа, разделённые пробелом: номер строки и номер позиции в строке.

Запишите в ответе два числа: сначала наибольшую длину цепочки из светлых точек, затем -- номер строки, в которой находится эта цепочка.

Пример входного файла:

7
1 2
2 3
3 6
2 4
1 3
2 5
2 4

При таких исходных данных имеется три цепочки светлых точек: в позициях 2 и 3 строки 1, в позициях 4, 5 и 6 строки 2 (это самая длинная цепочка!) и точка в позиции 6 строки 3. Ответ: 3 2.

(Е. Джобс) Игра «Заполни поле» заключается в том, чтобы заполнить прямоугольное поле, разбитое на квадраты. Игрок хочет написать программу, которая определила бы сколько есть позиций, в которые можно поместить горизонтальные блоки из четырех квадратов.

Входные данные представлены в файле 26-72.txt следующим образом. В первой строке записаны три числа N, M, K -- размер поля по горизонтали, размер поля по вертикали и количество занятых на поле квадратов. В каждой из следующих K строк записана пара чисел -- номера строки и столбца занятого квадрата.

Программа должна вывести пару чисел -- количество позиций в которые можно разместить горизонтальную линию из четырёх квадратов и номер ряда, в котором находится максимальное количество позиций для такого размещения. Если таких рядов несколько, выводится минимальный возможный номер.

Пример входного файла:

7 6 10
1 1
1 5
2 5
2 6
3 1
3 7
5 2
6 3
6 5
6 7

После анализа пар можем прийти к выводу, что имеем дело со следующим полем:

Расположить линию из четырех квадратов можно в 9 позициях (2;1), (3; 2), (3; 3), (4; 1), (4; 2), (4; 3), (4; 4), (5; 3), (5; 4). Максимальное количество позиций (4), в которых можно расположить фигуру, в 4 ряду. Ответ: 9 4.

(А. Кабанов) Маркетплейс с оптового склада каждый день отправляет заказанные товары в точки выдачи. Маркетплейс имеет множество видов различных товаров, каждый из которых имеет какой-то вес. Для отправки склад выделяет транспорт таким образом, чтобы отправить как можно больше товара каждого типа, но вес товаров одного типа не должен превышать S. Нужно определить, сколько всего товаров останется на складе и тип товара с самым большим остатком. Если таких товаров несколько, вывести товар с наименьшим кодом.

Входные данные представлены в файле 26-71.txt следующим образом. В первой строке входного файла записаны два числа, разделённые пробелом пробел: число N -- количество доступных товаров (натуральное число, не превышающее 10000) и число S -- вес, не более которого можно отправить каждый тип товара (натуральное число, не превышающее 10⁸). В каждой из следующих N строк записаны по два числа, разделённые пробелом: код товара (натуральное число, не превышающее 10⁹) и его вес (натуральное число, не превышающее 10⁵). Известно, что количество различных кодов товаров в файле не превышает тысячи.

Запишите в ответе два числа: сначала количество товаров, оставшихся на складе, а затем код товара с самым большим остатком.

Пример входного файла:

8 13
150 8
237 3
237 6
150 4
237 5
237 6
150 3
150 3

При таких исходных данных имеется всего два вида товаров (с кодами 150 и 237). Товаров с кодом 150 можно погрузить три штуки (3, 3 и 4), останется 1 штука (8). Товаров с кодом 237 можно погрузить две штуки (за 3 и 5), останется 2 штуки (6 и 6). Ответ: 3 237.

(А. Кабанов) На складе хранятся слитки металла различного веса. При отправке из одного или нескольких слитков формируется партия нужного веса, распил слитков не допускается. Складские запасы формируются так, чтобы из слитков можно было можно выдать партию любого веса, не превышающего суммарное количество металла на складе. Для этого должно выполняться следующее правило: вес каждого слитка не должен превышать суммарный вес меньших слитков более чем на 1.

Заведующий складом проводит ревизию с целью узнать, партии какого веса выдать со склада невозможно и исправляет это. Для этого он находит слитки, нарушающие это правило, и для каждого из них заказывается дополнительный слиток, исправляющий это нарушение. Заказываемые слитки при подсчёте не учитываются.

Для приведённого перечня слитков определите количество слитков, которые необходимо заказать и их суммарный минимальный вес.

Входные данные представлены в файле 26-70.txt следующим образом. В первой строке входного файла записано число N -- количество слитков (натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит одно число -- вес одного слитка (натуральное число, не превышающее 1 000 000).

Запишите в ответе два числа: сначала количество слитков, которое необходимо добавить на склад, затем их суммарный минимальный вес.

Пример входного файла:

4
1
4
1
11

При таких исходных данных два слитка не подходят под условие: 4 и 11. Для исправления будут заказаны слитки весом 1 и 4 (2 слитка общим весом 5). Ответ: 2 5.

(А. Кабанов) Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором наибольшее количеством подряд идущих мест, таких что все они уже распределены (заняты). В ответе запишите два целых числа: номер ряда и наибольшее количество подряд занятых мест.

Входные данные представлены в файле 26-69.txt следующим образом. В первой строке входного файла записано одно число: N -- количество занятых мест (натуральное число, не превышающее 10 000). Каждая из следующих N строк содержит пару чисел, разделённых пробелом: ряд и место выкупленного билета (натуральные числа, не превышающие 100000).

Запишите в ответе два числа: сначала номер ряда, затем наибольшее количество подряд занятых мест.

Пример входного файла:

10
5 5
5 6
5 7
16 9
16 3
16 6
20 23
20 28
20 29
20 30

В данном примере максимальное количество подряд идущих занятых мест равно 3 (5 ряд места 5, 6, 7 и 20 ряд места 28, 29,30). Ответ: 20 3.

(Л. Шастин) Компьютер был заражён вирусами. Супервирусами называются самые опасные вирусы, уровень опасности которых превышает средний уровень опасности всех имеющихся. Нужно определить, какое максимальное количество вирусов можно удалить за заданное время по следующим правилам:

-- необходимо удалить как можно больше супервирусов;

-- нельзя удалять два и более супервируса подряд;

-- нельзя удалять супервирус последним;

-- если существует более одного способа удалить одинаковое количество вирусов, следует выбрать тот, при котором будет затрачено меньшее количество времени.

Входные данные представлены в файле 26-68.txt следующим образом. Первая строка входного файла содержит количество записей N и общее время T, отведённое на удаление этих вирусов. Каждая из следующих N строк содержит два целых числа: уровень опасности вируса и время, которое требуется для его удаления.

Запишите в ответе два числа: сначала общее количество вирусов, которое удалось удалить, затем суммарное время, которое было затрачено на удаление супервирусов.

Пример входного файла:

5 50
7 13
9 20
4 3
8 9
5 5

Средний уровень опасности равен 6.6, значит, суперопасными считаются вирусы с уровнем опасности >= 7. Удаляем сначала супервирус 8-9, далее обычный вирус 4-3, потом снова суперопасный 7-13, затем обычный 5-5. Обычных вирусов не осталось, значит, суперопасные тоже удалять нельзя. Итого удалено 4 вируса. На удаление супервирусов затрачено времени 9 + 13 = 22. Ответ: 4 22.

Для анализа нагрузки сервера для каждого запроса в журнал записываются время начала и время завершения его обработки (в миллисекундах от момента начала исследований). Если начальное время равно 0, запрос начал обрабатываться до начала исследований, если конечное время равно 0, то обработка запроса закончилась после окончания исследований. Необходимо определить наименьшее количество запросов, которые сервер обрабатывал одновременно в течение суток, начиная с момента K, и суммарное время, в течение которого обрабатывалось это максимальное количество запросов.

Входные данные представлены в файле 26-66.txt следующим образом. Первая строка входного файла содержит количество записей N и время K. Каждая из следующих N строк содержит два целых числа: время начала и время завершения обработки одного запроса (в миллисекундах).

Запишите в ответе два числа: наименьшее количество запросов, которые сервер обрабатывал одновременно в течение указанных суток, и суммарное время, в течение которого обрабатывалось это минимальное количество запросов.

Пример входного файла (для заданного диапазона от 1000 до 6000):

6 1000
1300 2200
0 3700
1300 5700
0 0
5000 0
1800 3400

В данном случае наименьшее число запросов (2) выполнялось в интервале времени между 1000 и 1300, между 3700 и 5000, а также от 5700 до 6000 (общее время 300 + 1300 + 300 = 1900). Ответ: 2 1900.

Для анализа нагрузки сервера для каждого запроса в журнал записываются время начала и время завершения его обработки (в миллисекундах от момента начала исследований). Если начальное время равно 0, запрос начал обрабатываться до начала исследований, если конечное время равно 0, то обработка запроса закончилась после окончания исследований. Необходимо определить наибольшее количество запросов, которые сервер обрабатывал одновременно в течение суток, начиная с момента K, и суммарное время, в течение которого обрабатывалось это максимальное количество запросов.

Входные данные представлены в файле 26-66.txt следующим образом. Первая строка входного файла содержит количество записей N и время K. Каждая из следующих N строк содержит два целых числа: время начала и время завершения обработки одного запроса (в миллисекундах).

Запишите в ответе два числа: наибольшее количество запросов, которые сервер обрабатывал одновременно в течение указанных суток, и суммарное время, в течение которого обрабатывалось это максимальное количество запросов.

Пример входного файла (для заданного диапазона от 1000 до 6000):

6 1000
1300 2200
0 3700
1300 5700
0 0
5000 0
1800 3400

В данном случае наибольшее число запросов (5) выполнялось в интервале времени между 1800 и 2200. Ответ: 5 400.

На закупку товаров типов A, B, C, D и E выделена определённая сумма денег. Эти товары есть в продаже по различной цене. Необходимо на выделенную сумму закупить как можно больше товаров пяти типов (по общему количеству). Если можно разными способами купить максимальное количество пяти типов товаров, то нужно выбрать способ, при котором будет закуплено как можно больше товаров типа B. Если при этих условиях есть несколько способов закупки, нужно потратить как можно меньше денег.

Определите, сколько будет закуплено товаров типа B и сколько денег останется.

Входные данные представлены в файле 26-64.txt следующим образом. Первая строка входного файла содержит два целых числа: N -- общее количество товаров и M -- сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена товара в рублях) и символ (латинская буква), определяющий тип товара. Все данные в строках входного файла отделены одним пробелом.

Запишите в ответе два числа: сначала количество закупленных товаров типа B, затем оставшуюся неиспользованной сумму денег.

Пример входного файла:

6 110
40 E
50 A
50 B
30 C
20 B
10 A

В данном случае можно купить не более четырёх товаров, из них не более двух товаров типа B. Минимальная цена такой покупки 110 рублей (покупаем товары 10 A, 20 B, 30 C, 50 B). Останется 0 рублей. Ответ: 2 0.

На закупку товаров типов A, B, C, D и E выделена определённая сумма денег. Эти товары есть в продаже по различной цене. Необходимо на выделенную сумму закупить как можно больше товаров пяти типов (по общему количеству). Если можно разными способами купить максимальное количество пяти типов товаров, то нужно выбрать способ, при котором будет закуплено как можно больше товаров типа A. Если при этих условиях есть несколько способов закупки, нужно потратить как можно меньше денег.

Определите, сколько будет закуплено товаров типа A и сколько денег останется.

Входные данные представлены в файле 26-64.txt следующим образом. Первая строка входного файла содержит два целых числа: N -- общее количество товаров и M -- сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена товара в рублях) и символ (латинская буква), определяющий тип товара. Все данные в строках входного файла отделены одним пробелом.

Запишите в ответе два числа: сначала количество закупленных товаров типа A, затем оставшуюся неиспользованной сумму денег.

Пример входного файла:

6 110
40 E
50 A
50 D
30 C
20 B
10 A

В данном случае можно купить не более четырёх товаров, из них не более двух товаров типа A. Минимальная цена такой покупки 110 рублей (покупаем товары 10 A, 20 B, 30 C, 50 A). Останется 0 рублей. Ответ: 2 0.

На закупку товаров типов Q и Z выделена определённая сумма денег. Эти товары есть в продаже по различной цене. Необходимо на выделенную сумму закупить как можно больше товаров двух типов (по общему количеству). Если можно разными способами купить максимальное количество двух товаров, то нужно выбрать способ, при котором будет закуплено как можно больше товаров типа Q. Если при этих условиях есть несколько способов закупки, нужно потратить как можно меньше денег.

Определите, сколько будет закуплено товаров типа Q и сколько денег останется.

Входные данные представлены в файле 26-62.txt следующим образом. Первая строка входного файла содержит два целых числа: N -- общее количество товаров и M -- сумма выделенных на закупку денег (в рублях). Каждая из следующих N строк содержит целое число (цена товара в рублях) и символ (латинская буква Q или Z), определяющий тип товара. Все данные в строках входного файла отделены одним пробелом.

Запишите в ответе два числа: сначала количество закупленных товаров типа Q, затем оставшуюся неиспользованной сумму денег.

Пример входного файла:

6 110
40 Z
50 Q
50 Z
30 Z
20 Q
10 Z

В данном случае можно купить не более четырёх товаров, из них не более двух товаров типа Q. Минимальная цена такой покупки 110 рублей (покупаем товары 10 Z, 20 Q, 30 Z, 50 Q). Останется 0 рублей. Ответ: 2 0.

(Л. Шастин) Полина хранит на компьютере картинки и видео различного размера. Она хочет поместить как можно больше картинок и видео на флеш-накопитель, объём которого равен M Кбайт. Сначала она сохраняет самые маленькие видеозаписи до тех пор, пока они не займут не менее половины от общей памяти. В оставшееся место Полина сохраняет как можно больше картинок, стремясь занять весь оставшийся объём. Определите максимальное количество файлов (картинок и видео), которое Полина может сохранить на флеш-накопителе, и максимальный объём сохранённой картинки.

Входные данные представлены в файле 26-61.txt следующим образом. В первой строке записаны два числа: N -- количество всех изображений и видео, M -- объём флеш-накопителя (N и M -- натуральные числа, не превышающие 10⁶). В следующих N строках находятся значения объёмов картинок и видео в Кбайтах. Информационный объём каждой картинки не более 100 Кбайт, объём видео -- не менее 101 Кбайт.

Запишите в ответе два числа: сначала общее количество картинок и видео, которые могут быть сохранены, затем -- максимальный объём сохранённой картинки.

Пример входного файла:

8 150
20
101
15
400
5
900
10
9

При таких исходных данных можно сохранить 4 картинки и 1 видео объёмом 101, всего 4 + 1 = 5 элементов. При этом максимальный объём сохранённой картинки равен 20 (например, 20+10+9+5). Ответ: 5 20.

(А. Богданов) В некотором государстве правительство выделяет K специальностей для обучения студентов. На эти места претендуют N абитуриентов. Для каждой специальности задано количество мест. Для каждого абитуриента известны его баллы и одна выбранная им специальность. Зачисление осуществляется в одну волну. На направление зачисляются абитуриенты с максимальными баллами. Требуется определить общее количество зачисленных абитуриентов и минимальный балл студента, зачисленного на специальность с максимальным конкурсом.

Входные данные представлены в файле 26-60.txt следующим образом. В первой строке через пробел записаны два целых числа K и N. В следующих K строках записано по одному числу -- количеством мест по каждой специальности. Следующие N строк содержат пары чисел: баллы студента (до 300 включительно) и код выбранной специальности (начиная с 0).

В ответе запишите два целых числа: общее количество зачисленных абитуриентов и минимальный балл студента, зачисленного на специальность с максимальным конкурсом.

Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий условию.

Входные данные представлены в файле 26-59.txt следующим образом. В первой строке входного файла находится одно число: N -- количество занятых мест (натуральное число, не превышающее 10 000). В следующих N строках находятся пары чисел: ряд и место выкупленного билета, не превышающие 100 000.

В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.

Пример входного файла:

10
5 5
5 9
5 6
16 9
16 3
16 6
20 23
20 28
20 35
20 40

В данном примере есть следующие свободные места, удовлетворяющие условию: 7 и 8 в ряду 5, 4 и 5 в ряду 16, а также 7 и 8 в ряду 16. Выбираем наибольший номер ряда: 16 и наименьший номер места: 4. В ответе нужно указать: 16 4.

(А. Комков) Магазин «1000 мелочей» закупает у поставщика продукцию для дальнейшей перепродажи. Известно количество товаров на складе у поставщика и стоимость каждого из них. К сожалению, бюджет магазина ограничен, поэтому принято решение закупить как можно больше товаров на ту сумму, которой располагает магазин, причем закупают не менее двух товаров с каждой ценой. По заданной информации о цене каждого товара и бюджете магазина, определите

1)    максимальную возможную стоимость товара, который можно купить при условии, что закупили максимально возможное количество товаров;
2)    наибольшее количество купленных товаров, у которых одинаковая цена.

Входные данные представлены в файле 26-58.txt следующим образом. В первой строке входного файла находятся два числа: S -- размер бюджет магазина (натуральное число, не превышающее 100 000) и N -- количество товаров на складе у поставщика (натуральное число, не превышающее 10000). В следующих N строках находятся значения цена каждого товара у поставщика (все числа натуральные, не превышающие 100), каждое в отдельной строке.

Запишите в ответе два числа: сначала максимальную стоимость купленного товара, затем максимальное количество купленных товаров с одинаковой ценой.

Пример входного файла:

100 9
20
30
20
5
10
15
10
30
10

В данном примере можно закупиться следующим образом: 10 10 10 20 20, либо 10 10 10 30 30. В первом случае максимальная стоимость товара будет 20, а во втором -- 30. Наибольшее количество товаров с одинаковой ценой в обоих случаях равно 3. В ответе нужно указать: 30 3.

(А. Богданов) Начинающему админу Ване для тренировки выдали аппарат для сварки оптоволокна и N кусков оптоволокна, из которых попросили получить цельные куски по M метров. С целью снижения затухания сигнала в полученном кабеле нужно минимизировать количество сварок. Да и работы меньше. Укажите в ответе два числа: сколько всего сварок будет в цельных кусках и сколько останется кусков, из которых не сварить цельный кусок требуемой длины. Ваня выбирал куски строго по уменьшению длины, за исключением последнего, который выбирался исходя из минимизации длины каждого обрезка. Обрезок идет обратно в пучок кусков для следующего использования.

Входные данные представлены в файле 26-57.txt следующим образом. В первой строке входного файла записаны значения N (количество кусков оптоволокна) и M (длина необходимого цельного куска). Каждая из следующих N строк содержит одно целое число -- длину очередного куска.

Пример входного файла:

10 30
17 15 14 12 11 8 6 5 4 2

Сперва взяли 17 и 14, обрез 1 обратно в кучу \[15,12,11,8,6,5,4,2,1\] -- одна сварка. Затем взяли 15,12 и 4, обрез длиной 1 обратно в кучу \[11,8,6,5,2,1,1\] -- две сварки. И затем взяли 11,8,6 и 5, ровно 30, без обреза -- три сварки. Итого: 6 сварок и 3 оставшихся куска оптоволокна.