Шеф
Шеф
Перед святами Шеф отримує дуже багато запрошень на святкові засідання. Щоб краще планувати свій час, Шеф увів правило, щоб у кожному запрошенні був чітко вказаний відрізок часу [ ai
; bi
], коли триває засідання. Крім того, Шеф встановлює кожному засіданню "важливість" ci
.
Шеф не любить половинчатих рішень, тому або перебуває на засіданні увесь вказаний час, або не приходить на нього зовсім. Між відвідинами засідань має бути хоча б мінімальна перерва, тобто Шеф може устигнути на j-те (за списком запрошень) після i-го, тоді й тільки тоді, коли aj
> bi
.
Напишіть програму, що допомагатиме Шефу відвідати засідання з якомога більшою сумою важливості. Якщо можливі різні набори засідань з однаковою максимальною сумарною важливістю, вибрати той, де менша сумарна тривалість засідань.
Вхідні дані:
Програма читає з клавіатури спочатку кількість заходів N, де 2 ≤ N ≤ 98765, потім N трійок
(ai
, bi
, ci
). Гарантовано, що 0 ≤ ai
< bi
< 109
, усі ci
натуральні та їхня сума не перевищує 109
.
Вихідні дані
Програма має вивести на екран через пропуск суму важливості та суму тривалості вибраних засідань.
3 1 5 3 4 9 4 6 11 2
5 9
3 1 5 3 5 9 5 6 11 2
5 4