Перед святами Шеф отримує дуже багато запрошень на святкові засідання. Щоб краще планувати свій час, Шеф увів правило, щоб у кожному запрошенні був чітко вказаний відрізок часу [ ai; bi ], коли триває засідання. Крім того, Шеф встановлює кожному засіданню "важливість" ci.

Шеф не любить половинчатих рішень, тому або перебуває на засіданні увесь вказаний час, або не приходить на нього зовсім. Між відвідинами засідань має бути хоча б мінімальна перерва, тобто Шеф може устигнути на j-те (за списком запрошень) після i-го, тоді й тільки тоді, коли aj > bi.

Напишіть програму, що допомагатиме Шефу відвідати засідання з якомога більшою сумою важливості. Якщо можливі різні набори засідань з однаковою максимальною сумарною важливістю, вибрати той, де менша сумарна тривалість засідань.

Вхідні дані:

Програма читає з клавіатури спочатку кількість заходів N, де 2 ≤ N ≤ 98765, потім N трійок (ai, bi, ci). Гарантовано, що 0 ≤ ai < bi < 109, усі ci натуральні та їхня сума не перевищує 109.

Вихідні дані

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