Banknotes for a New Game

Time limit2sMemory limit128 MB

Summary

Choose K denominations starting at 1 won where each next one is 2, 3, 4, or 5 times the previous, to minimize the number of banknotes summing to N won.

Level: Hard8 of 10
Topics: Dynamic programming, Math, Number theory, Recursion
Solved: No attempts yet

Problem

A game uses banknotes as its currency. The set of banknote denominations must satisfy the following conditions.

There are exactly K distinct denominations.
The smallest denomination is 1 won.
For each i, the i-th denomination is 2, 3, 4, or 5 times the (i-1)-th denomination.

A player receives N won at the start of the game. For the same amount of money, using fewer banknotes is better. You may choose any denomination set satisfying the conditions. Find the minimum number of banknotes needed to make exactly N won.

Input

The input contains two integers N and K.

Output

Print the minimum number of banknotes needed to make N won.

Constraints

1 ≤ N ≤ 10^18
1 ≤ K ≤ 100

Examples5

Example 1
Input
```
1025
6
```
Expected output
```
2
```
Example 2
Input
```
1005
5
```
Expected output
```
3
```
Example 3
Input
```
12000
14
```
Expected output
```
1
```

Example 4

Input

924323565426323626
1

Expected output

924323565426323626

Example 5
Input
```
924323565426323626
50
```
Expected output
```
10
```