### Problem Statement

You are creating the money system for a new game. The requirements are as follows:

1. There will be exactly K different banknote values.
2. The value of the smallest banknote will be equal to one dollar.
3. The value of the i-th banknote will be equal to the value of the (i-1)-th banknote multiplied by 2, 3, 4 or 5.

The initial capital of a player will be N dollars, so you want to choose banknote values in such a way that minimizes the number of banknotes required to make N dollars. Assume that you have an infinite supply of banknotes for each value.

You will be given two integers N and K. Due to technical reasons, N will be given as a String with no leading zeros. Return the minimal number of banknotes required to make exactly N dollars. Note that you must minimize the number of actual banknotes, not the number of banknote values (see examples).

### Definition

 Class: NewMoneySystem Method: chooseBanknotes Parameters: String, int Returns: long Method signature: long chooseBanknotes(String N, int K) (be sure your method is public)

### Constraints

-N will be an integer between 1 and 1018, inclusive, with no leading zeros.
-K will be between 1 and 100, inclusive.

### Examples

0)

 `"1025"` `6`
`Returns: 2`
 The best set of banknote values is {1, 4, 16, 64, 256, 1024}. 1025 = 1024 + 1.
1)

 `"1005"` `5`
`Returns: 3`
 The best set of banknote values is {1, 5, 25, 100, 500}. 1005 = 2 * 500 + 5.
2)

 `"12000"` `14`
`Returns: 1`
3)

 `"924323565426323626"` `1`
`Returns: 924323565426323626`
 The answer can be rather big.
4)

 `"924323565426323626"` `50`
`Returns: 10`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10005&pm=6828

Andrew_Lazarev

#### Testers:

PabloGilberto , brett1479 , Yarin , Olexiy

#### Problem categories:

Dynamic Programming