В обігу перебувають банкноти номіналами 1, 2, 5, 10, 20, 50, 100, 200 та 500 гривень.Всередині Супер-Пупер-Банкомату є в наявності великі запаси кожного з цих номіналів.Якою мінімальною кількістю банкнот цей банкомат може видати суму S?Перед святами Шеф отримує дуже багато запрошень на святкові засідання. Щоб краще планувати свій час, Шеф увів правило, щоб у кожному запрошенні був чітко вказаний відрізок часу [ 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
.
Програма має вивести на екран через пропуск суму важливості та суму тривалості вибраних засідань.####Вхідні дані.
Єдине ціле число S, 1 ≤ S ≤ 12345.
Єдине ціле число - мінімальна кількість банкнот, якою можна видати вказану суму.
####Приімтка.2018 можна видати як 500+500+500+500+10+5+2+1, тобто вісьмома банкнотами.Ще меншою кількістю банкнот вказаних номіналів видати суму 2018 неможливо.