Minimum Number of Coins

Minimum Number of Coins

Given a set of coin denominations, find the minimum number of coins needed to make a given amount.

Input format

The first line contains AMOUNT (1 ≤ AMOUNT ≤ 5000).

Output format

Print the minimum number of coins needed. Available denominations: 1, 2, 5, 10, 20, 50, 100, 500, 1000.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

1

1

5

1