(Д. Муфаззалов) На парковке расположены парковочные места для M категорий автомобилей. Номер категории -- целое неотрицательное число, меньшее, чем M. Для каждой категории автомобилей выделено некоторое количество парковочных мест. Приезжающий на парковку автомобиль занимает любое свободное место среди мест, предназначенных для автомобилей его категории, а также среди мест, предназначенных для автомобилей c бóльшим номером категории. Автомобиль всегда паркуется на подходящем свободном месте для автомобилей с наименьшей категорией. Если подходящего свободного места нет, автомобиль уезжает. Гарантируется, что никакие два автомобиля не приезжают одновременно. Если время прибытия автомобиля совпадает со временем окончания стоянки другого автомобиля, вновь прибывший автомобиль может занять освободившееся место, если оно подходит ему.
Пусть K -- минимальный номер категории парковочных мест, в которой за всё время припарковалось наибольшее количество автомобилей. Определите время, через которое освободятся (и больше не будут заняты) все парковочные места категории K, и количество автомобилей, которые парковались на местах категории K.
Входные данные представлены в файле 26-120.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: M -- количество категорий автомобилей, 1 ≤ M \< 525 600, и N -- общее количество автомобилей, приехавших на парковку в течение одного года, 0 ≤ N ≤ 106. Вторая строка содержит M чисел -- количество парковочных мест на стоянке для автомобилей каждой категории, начиная с категории под номером 0, в порядке возрастания номеров категорий. Каждое из этих чисел не превышает 1000. Каждая из N последующих строк описывает один автомобиль и содержит три целых числа: время в минутах с начала года, когда автомобиль прибыл на парковку; необходимую длительность стоянки в минутах и номер категории автомобиля.
В ответе запишите два целых числа: время освобождения парковочных мест категории K, затем -- общее количество автомобилей, которые парковались на местах категории 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) не найдет место. В категории мест с номером 0 припарковалось максимальное количество автомобилей -- 2, все парковочные места категории 0 освободились на 29-й минуте. Ответ: 29 2.