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

Вхідні дані.

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

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

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

Примітка.

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