Шеф
Перед праздниками Шеф получает множество приглашений на праздничные заседания. Чтобы лучше организовать своё время, он требует, чтобы в каждом приглашении был чётко указан временной интервал [ a[i]; b[i] ], в который проходит заседание. Кроме того, каждое заседание имеет свою "важность" c[i].
Шеф предпочитает либо полностью присутствовать на заседании, либо не посещать его вовсе. Между посещениями заседаний должна быть минимальная пауза, то есть Шеф может пойти на j-е заседание после i-го, только если a[j] > b[i].
Напишите программу, которая поможет Шефу выбрать такие заседания, чтобы сумма их важности была максимальной. Если существуют разные наборы заседаний с одинаковой максимальной суммарной важностью, выберите тот, где суммарная продолжительность заседаний минимальна.
Входные данные
Программа сначала считывает количество мероприятий N (где 2 ≤ N ≤ 98765), а затем N троек(a[i], b[i], c[i]), каждая в отдельной строке. Гарантируется, что 0 ≤ a[i] < b[i] < 2^31 = 2147483648, все c[i] натуральные, и их сумма не превышает 10^9.
Выходные данные
Программа должна вывести через пробел сумму важности и сумму продолжительности выбранных заседаний.