Spremajući se za put u Egipat, Miloš je čitao o novčanom sistemu u drevnom Egiptu. Otkrio je da su postojale samo novčanice u vrednosti ~d \cdot 10^k~ za za svako ~d~ iz skupa ~\{ 1,2,5 \}~, i svaki nenegativan ceo broj ~k~, tj. novčanice u vrednosti ~\{1,2,5,10,20,50,100,200,500,\ldots\}~. Razmišljajući o ovome, Miloš se zapitao koliko je najmanje novčanica potrebno da se isplati neka suma ~V~?

Opis ulaza

U prvom redu nalazi se nenegativan ceo broj ~V~, suma koju je potrebno isplatiti.

Opis izlaza

Ispisati najmanji broj novčanica, potrebnih da se isplati data suma.

Primer 1

Ulaz

42

Izlaz

3

Primer 2

Ulaz

121412181214

Izlaz

16

Objašnjenje primera 1

U datom primeru, sumu možemo isplatiti koristeći ~2~ novčanice vrednosti ~20~ i jedne novčanice vrednosti ~2~.

Ograničenja

• ~1 \leq V < 10^{18}~

Test primeri su podeljeni u četiri disjunktne grupe:

• U test primerima vrednim 20 poena: ~V < 10~.
• U test primerima vrednim 20 poena: Broj ~V~ se sastoji samo od cifara ~1~, ~2~ i ~5~.
• U test primerima vrednim 45 poena: ~V < 10^9~.
• U test primerima vrednim 15 poena: Nema dodatnih ograničenja.