eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

Шеф

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

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

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

Програма має вивести на екран через пропуск суму важливості та суму тривалості вибраних засідань.

Пример

Входные данные #1
3
1 5 3
4 9 4
6 11 2
Выходные данные #1
5 9
Входные данные #2
3
1 5 3
5 9 5
6 11 2
Выходные данные #2
5 4