Money Changing

Submit solution
Points: 1 (partial)
Time limit: 1.0s
Memory limit: 98M
Author:
nguyennghia_nh
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Minh go shopping at the SS shop. The shop has currency denominations: 1$,5$,10$,50$,100$,500$.

Minh takes some items at the shop and pay an amount of 1000$. Your task to devise a method to pay back amount to customer using fewest number of money notes.

Input

The input consists of only one single integer N (1≤N≤999) denoting the total value of the taken items.

Output

The output consists of only one single integer denoting the number of money notes.

Example

Input

Copy
380

Output

Copy
4

Explanation

The shop has to pay back 620$ by giving one paper of 500$, one paper of 100$ and two papers of 10$.

Comments

There are no comments at the moment.