Супер-Пупер-Банкомат

В обігу перебувають банкноти номіналами 1, 2, 5, 10, 20, 50, 100, 200 та 500 гривень.Всередині Супер-Пупер-Банкомату є в наявності великі запаси кожного з цих номіналів.Якою мінімальною кількістю банкнот цей банкомат може видати суму S?

Input

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

Output

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

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

Examples