В файле записаны данные о работе склада в течении года (365 дней): для хранения каждого товара указаны время начала хранения и время конца хранения в днях от 1 января. Всего на складе есть N ячеек для хранения товаров на стеллажах, для каждой ячейки определена суточная стоимость хранения в ней товара (в зависимости от удобства доступа и уровня стеллажа). При поступлении товара для него выделяется свободная ячейка с минимальной стоимостью хранения, а если таких ячеек несколько, выбирается ячейка с минимальным номером. Определите номер ячейки, за хранение товаров в которой в течение года склад получил наибольшую сумму (если таких ячеек несколько, выберите ячейку с наибольшим номером), и наибольшее количество разных товаров, которое хранилось в течение года в одной ячейке.
Входные данные представлены в файле 26-185.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. Наибольшую сумму, равную 65700, склад получил за хранение товаров в ячейке 101. Наибольшее количество товаров (2) хранилось в ячейке 102. Ответ: 101 2.