В файле записаны данные о работе склада в течении года (365 дней): для хранения каждого товара указаны время начала хранения и время конца хранения в днях от 1 января. Всего на складе есть N ячеек для хранения товаров на стеллажах, для каждой ячейки определена суточная стоимость хранения в ней товара (в зависимости от удобства доступа и уровня стеллажа). При поступлении товара для него выделяется свободная ячейка с минимальной стоимостью хранения, а если таких ячеек несколько, выбирается ячейка с минимальным номером. Определите общую сумму, которая была выручена складом за хранение товаров в течение года, и номер ячейки, в которой был размещён последний товар, поступивший на склад.
Входные данные представлены в файле 26-185.txt следующим образом. В первой строке входного файла находится натуральное число N (N ≤ 1000) – количество ячеек на складе, и натуральное число K (K ≤ 100 000) – количество записей о хранении товаров. Следующие N строк содержат по одному числу – стоимости хранения товаров в ячейках (за сутки) в порядке нумерации ячеек, начиная с первой. Каждая из следующих K строк содержат два натуральных числа, не превышающие 365: время начала хранения и время окончания хранения товара.
Запишите в ответе два натуральных числа: сначала общую сумму, которая была выручена складом за хранение товаров в течение года, затем – номер ячейки, в которой был размещён последний товар, поступивший на склад.
Пример входного файла:
2 3
300
100
40 150
122 340
300 360
При таких исходных первый товар помещается в ячейку 2 (стоимость 100), второй – в ячейку 1, третий – в ячейку 2. За хранение первого товара будет получено 100·(150 – 40 + 1) = 11100, за хранение второго товара – 300·(340 – 122 + 1) = 65700, за хранение третьего товара – 100·(360 – 300 + 1) = 6100. Общая сумма – 82900. Ответ: 82900 2.