Перед святами Шеф отримує дуже багато запрошень на святкові засідання. Щоб краще планувати свій час, Шеф увів правило, щоб у кожному запрошенні був чітко вказаний відрізок часу [ 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]
< 10^9
, усі c[i]
натуральні та їхня сума не перевищує 10^9
.
Програма має вивести на екран через пропуск суму важливості та суму тривалості вибраних засідань.