10044 동전 거스름돈 Silver III

문제

1원, 5원, 10원, 50원, 100원, 500원짜리 동전이 무한히 있다. 거스름돈 N원을 동전으로 만들 때 필요한 최소 동전 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 거스름돈 N (1 ≤ N ≤ 1,000,000)이 주어진다.

출력

최소 동전 개수를 출력한다.

1260

6