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.