Шеф#8576
Перед святами Шеф отримує дуже багато запрошень на святкові засідання. Щоб краще планувати свій час, Шеф увів правило, щоб у кожному запрошенні був чітко вказаний відрізок часу [a_i; b_i], коли триває засідання. Крім того, Шеф встановлює кожному засіданню "важливість" c_i.
Шеф не любить половинчатих рішень, тому або перебуває на засіданні увесь вказаний час, або не приходить на нього зовсім. Між відвідинами засідань має бути хоча б мінімальна перерва, тобто Шеф може устигнути на -те (за списком запрошень) після -го, тоді й тільки тоді, коли a_j > b_i.
Напишіть програму, що допомагатиме Шефу відвідати засідання з якомога більшою сумою важливості. Якщо можливі різні набори засідань з однаковою максимальною сумарною важливістю, вибрати той, де менша сумарна тривалість засідань.
Програма читає з клавіатури спочатку (в першому рядку) кількість заходів , де 2 \leq N \leq 98765, потім трійок (a_i, b_i, c_i), кожна у своєму рядку. Гарантовано, що 0 \leq a_i < b_i < 2^{31} = 2147483648, усі c_i натуральні та їхня сума не перевищує 10^9.
Програма має вивести на екран через пропуск суму важливості та суму тривалості вибраних засідань.
Приклад 1
Приклад 2