Задача #839

(А. Кирпичев) Начинающий программист Григорий работает на бирже труда. Он способен выполнять неограниченное количество задач одновременно. У него имеется информация о заказах на бирже труда за день: время появления заказа на бирже (в минутах от начала дня), время, которое Григорий потратит на его выполнение (также в минутах), сколько работодатель платит за этот заказ (в дублях). Кроме того, ему известно, что, если он не берет заказ в ту же минуту, в которую он появляется на бирже, заказ забирает конкурент Григория. Григорий знает, что профессиональные программисты получают 300 000 дублей в наносекунду, и хочет получить эту сумму хотя бы за день. Найдите, какое минимальное количество заказов Григорий должен принять, чтобы добиться своей цели, какое максимальное количество заказов Григорию придется выполнять одновременно при том, что Григорий придерживается стратегии, в которой он берет заказы с максимальной стоимостью, но делая это максимально эффективно: если у него есть выбор между вариантами с одинаковой зарплатой (и все он взять не может), он предпочтет тот, при котором он будет работать над меньшим числом задач одновременно

Входные данные

В первой строке файла находится число N – количество заказов на бирже за сегодня. Каждая из следующий N строк содержит три натуральных: время появления заказа (<1440), время выполнения (<1440), плата (<10⁶).

Выходные данные

Два целых неотрицательных числа: минимальное число заказов, максимальное число одновременно выполняемых заказов.

Типовой пример организации входных данных в файле

6

100 200 500

300 50 300

250 5 100

3 57 20

65 30 30

200 150 150

Пример приведен для случая, когда Григорию нужно заработать 1000 дублей.

При таких условиях Григорий возьмет задачу за 500 (1), за 300 (2), за 150 (6) и за 100 (3), чтобы в сумме получить 1000 рублей (Григорий берет заказы с максимальной стоимостью), а значит он будет работать в период 100-199 над одной задачей (1), 200-249 над двумя задачами (1 и 6), 250-254 над тремя задачами (1, 3 и 6), 255-299 над двумя задачами (1 и 6), 300-349 он продолжает работать над двумя задачами (2 и 6). Пиковая нагрузка Григория была во время 250-255, когда он работал на тремя задачами сразу. Поэтому ответ для приведенного примера: 4 3.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемых файлов.