(Д. Муфаззалов) На парковке расположены парковочные места для M категорий автомобилей. Номер категории -- целое неотрицательное число, меньшее, чем M. Для каждой категории автомобилей выделено некоторое количество парковочных мест. Приезжающий на парковку автомобиль занимает любое свободное место среди мест, предназначенных для автомобилей его категории, а также среди мест, предназначенных для автомобилей c бóльшим номером категории. Автомобиль всегда паркуется на подходящем свободном месте для автомобилей с наименьшей категорией. Если подходящего свободного места нет, автомобиль уезжает. Гарантируется, что никакие два автомобиля не приезжают одновременно. Если время прибытия автомобиля совпадает со временем окончания стоянки другого автомобиля, вновь прибывший автомобиль может занять освободившееся место, если оно подходит ему.
Пусть K -- максимальный номер категории автомобилей, в которой за всё время припарковалось наибольшее количество автомобилей. Определите время, через которое освободятся (и больше не будут заняты) все парковочные места, предназначенные для категории автомобилей с номером K, и общее количество автомобилей всех категорий, которые уедут из-за отсутствия мест.
Входные данные представлены в файле 26-120.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: M -- количество категорий автомобилей, 1 ≤ M \< 525 600, и N -- общее количество автомобилей, приехавших на парковку в течение одного года, 0 ≤ N ≤ 106. Вторая строка содержит M чисел -- количество парковочных мест на стоянке для автомобилей каждой категории, начиная с категории под номером 0, в порядке возрастания номеров категорий. Каждое из этих чисел не превышает 1000. Каждая из N последующих строк описывает один автомобиль и содержит три целых числа: время в минутах с начала года, когда автомобиль прибыл на парковку; необходимую длительность стоянки в минутах и номер категории автомобиля.
В ответе запишите два целых числа: время освобождения парковочных мест для автомобилей категории K, затем -- общее количество автомобилей всех категорий, которые уедут из-за отсутствия мест.
Пример входного файла:
2 5
2 1
5 22 0
8 30 1
14 15 0
25 12 0
20 40 1
При таких исходных данных: 1-й автомобиль (категории 0) припаркуется на месте категории 0 с 5 по 27 минуты, 2-й автомобиль (категории 1) припаркуется на месте категории 1 с 8 по 38 минуты,
3-й автомобиль (категории 0) припаркуется на месте категории 0 с 14 по 29 минуты, 4-й автомобиль (категории 0) не найдет место, 5-й автомобиль (категории 1) не найдет место. В максимальное количество припаркованных автомобилей (2) имели категорию 0, все парковочные места для автомобилей категории 0 (т. е. места категорий 0 и 1) освободились на 38-й минуте. Ответ: 38 2.