Задание №26: Обработка данных с помощью сортировки

В файле записаны данные о работе склада в течении года (365 дней): для хранения каждого товара указаны время начала хранения и время конца хранения в днях от 1 января. Всего на складе есть N ячеек для хранения товаров на стеллажах, для каждой ячейки определена суточная стоимость хранения в ней товара (в зависимости от удобства доступа и уровня стеллажа). При поступлении товара для него выделяется свободная ячейка с минимальной стоимостью хранения, а если таких ячеек несколько, выбирается ячейка с минимальным номером. Определите наибольшую сумму, которая была выручена складом за хранение товаров в одной ячейке в течение года, и номер ячейки, в которой хранилось (в разное время) наибольшее количество разных товаров. Если таких ячеек несколько, выберите ячейку с наибольшим номером.
Входные данные представлены в файле 26-186.txt следующим образом. В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество ячеек на складе, и натуральное число K (K ≤ 100 000) – количество записей о хранении товаров. Следующие N строк содержат по два натуральных числа, не превышающие 1000 – номер ячейки и стоимость хранения товаров в ячейке (за сутки). Каждая из следующих K строк содержит два натуральных числа, не превышающие 365: время начала хранения и время окончания хранения товара. Запишите в ответе два натуральных числа: сначала общую сумму, которая была выручена складом за хранение товаров в одной ячейке в течение года, затем – номер ячейки, в которой хранилось наибольшее количество разных товаров.
Пример входного файла:

2 3
101 300
102 100
40 150
122 340
300 360

При таких исходных первый товар помещается в ячейку 102 (стоимость 100), второй – в ячейку 101, третий – в ячейку 102. За хранение первого товара будет получено 100·(150 – 40 + 1) = 11100, за хранение второго товара – 300·(340 – 122 + 1) = 65700, за хранение третьего товара – 100·(360 – 300 + 1) = 6100. Наибольшая сумма, полученная складом за хранение товаров в одной ячейке (ячейке 101) равна 65700. Наибольшее количество товаров (2) хранилось в ячейке 102. Ответ: 65700 102.