### Problem Statement

The monetary system in Absurdistan is really simple and systematic. The locals only use coins. The coins come in different values. The values used are:

1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000, ...

Formally, for each K>=0 there are coins worth 10K, and coins worth 25*100K.

You want to buy a new car. Its price is cost. Write a method that will return the smallest number of coins necessary to pay exactly the cost of the car (assuming you have a sufficient supply of coins of each of the types you will need).

### Definition

 Class: AnotherCoinProblem Method: minimumCoins Parameters: long Returns: int Method signature: int minimumCoins(long cost) (be sure your method is public)

### Constraints

-cost will be between 1 and 10^15, inclusive.

### Examples

0)

 `47`
`Returns: 5`
 The best way to pay 47 is 25+10+10+1+1.
1)

 `9`
`Returns: 9`
 To pay 9, we can only use nine coins worth 1 each.
2)

 `250111`
`Returns: 4`
3)

 `76540123`
`Returns: 16`
 3*25,000,000 + 1*1,000,000 + 2*250,000 + 4*10,000 + 1*100 + 2*10 + 3*1 = 76,540,123 3 + 1 + 2 + 4 + 1 + 2 + 3 = 16

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10285

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13730&pm=10285

misof

#### Testers:

PabloGilberto , Olexiy , ivan_metelsky

#### Problem categories:

Brute Force, Dynamic Programming, Greedy, Recursion