우주 화폐

우주 연합에서 사용하는 화폐의 동전 단위는 다음과 같다:

1, 10, 25, 100, 1000, 2500, 10000, 25000, ...

즉, 각 자리(2자리씩 묶은)마다 단위 1, 10, 25가 사용된다.

어떤 가격이 주어졌을 때, 정확히 그 금액을 지불하기 위해 필요한 최소 동전 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 가격이 주어진다. (1 <= 가격 <= 10^15)

출력

최소 동전 수를 출력한다.

입출력 예시

입력 1

30

출력 1

3

입력 2

50

출력 2

2