Busskortet

Du ska köpa ett busskort. Det är ett påtankningskort som du laddar med pengar, därefter kan du åka på kortet tills pengarna tagit slut. Du vet att du ska åka för $K$ kronor, där $K \leq 10\, 000$. Att ladda kortet tar sin tid eftersom du endast kan ladda kortet med $500$, $200$ eller $100$ kr i taget. Du har för tillfället bråttom och vill därför utföra så litet antal transaktioner som möjligt, men aldrig tanka på mer pengar än nödvändigt.

Om du ska åka för 800 kronor ska du alltså först ladda med 500, sen med 200, därefter med 100 kr. Om du däremot ska åka för 850 kronor ska du först ladda med 500 och därefter ladda med 200 två gånger. Visserligen går 50 kronor till spillo, men det är ändå det bästa alternativet.

Skriv ett program som beräknar det minsta antalet transaktioner du behöver göra.

Input

Indatan består av heltalet $1 \le K \le 10\, 000$, det vill säga antalet kronor du ska åka för.

Output

Ditt program ska skriva ut ett enda heltal: det minsta antalet transaktioner du behöver göra.

Poängsättning

Ditt program kommer testas på tre olika testfall. Om du klarar två av dessa får du $50$ poängg. Om du klarar alla tre får du $100$ poäng.

850

3

1800

5