Back to problems
IntermediateGreedy2000 ms256 MB

Market Change

Given item cost and cash paid in Jamaican dollars, output the minimum number of bills/coins for the change using denominations 5000, 1000, 500, 100, 50, 20, 10, 5, and 1.

Statement

Given item cost and cash paid in Jamaican dollars, output the minimum number of bills/coins for the change using denominations 5000, 1000, 500, 100, 50, 20, 10, 5, and 1.

Input

Two integers: cost and paid.

Output

Minimum number of bills/coins returned.

Constraints

  • `0 <= cost <= paid <= 100000`

Examples

Example 1

Input

1375 2000

Output

4

Change is 625: 500, 100, 20, and 5.

Sample runs use visible examples. Full submissions are checked securely on the server, and private test cases are not shown in the browser.