В обігу перебувають банкноти номіналами 1, 2, 5, 10, 20, 50, 100, 200 та 500 гривень. Всередині Супер-Пупер-Банкомату є в наявності великі запаси кожного з цих номіналів. Якою мінімальною кількістю банкнот цей банкомат може видати суму S? Перед святами Шеф отримує дуже багато запрошень на святкові засідання. Щоб краще планувати свій час, Шеф увів правило, щоб у кожному запрошенні був чітко вказаний відрізок часу [ ai; bi ], коли триває засідання. Крім того, Шеф встановлює кожному засіданню "важливість" ci.

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

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

Вхідні дані:

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

Вихідні дані

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

Вхідні дані.

Єдине ціле число S, 1 ≤ S ≤ 12345.

Вихідні дані.

Єдине ціле число - мінімальна кількість банкнот, якою можна видати вказану суму.

Приімтка.

2018 можна видати як 500+500+500+500+10+5+2+1, тобто вісьмома банкнотами. Ще меншою кількістю банкнот вказаних номіналів видати суму 2018 неможливо.