Você foi visitar um país cujas moedas são: 1 dinheiros, 5 dinheiros, 10 dinheiros, 25 dinheiros, 50 dinheiros e 100 dinheiros.

Um amigo seu mora nesse país e gosta de vender tortas, porém, devido a uma de suas manias, ele gosta sempre de dar o troco com o menor número de moedas possíveis. Como ele sabe que você é um ótimo programador, ele pediu que você faça um programa que o ajude a alcançar esse propósito.

Entrada

A entrada contém um único número $N$, o valor do troco que seu amigo tem que dar.

Saída

Seu programa deve imprimir o menor número de moedas que seu amigo deve usar para dar esse troco.

Restrições

• $1 \leq N \leq 1000000$

Exemplos de Entrada	Exemplos de Saída
50	1
84	7

Para submeter sua solução, use esse link.