Changing Digits

Time limit1sMemory limit1024 MB

Summary

Find the largest number reachable from N by changing one digit at a time so that each new value's remainder modulo M strictly increases.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Math
Solved: No attempts yet

Statement

Dovydas told Justas two natural numbers $N$ and $M$ . Justas's task is to turn $N$ into the largest possible number. He may do this by changing $N$ one digit at a time, so that after each change the remainder of the number divided by $M$ strictly increases. When changing a digit, the leading digit may not be changed to $0$ .

For example, if $N = 1399$ and $M = 11$ , then the remainder of $N$ divided by $M$ is initially $1399 \bmod 11 = 2$ . If Justas first changes the last digit of $N$ , he may choose it among $0, 1, \dots, 6$ , because these options increase the remainder:

N	1390	1391	1392	1393	1394	1395	1396	1397	1398	1399
remainder	4	5	6	7	8	9	10	0	1	2

Suppose he chooses $3$ , so $N$ is now $1393$ . If Justas now changes the leading digit, the only possible value is $9$ (note that the leading digit may not be changed to $0$ ):

N	1393	2393	3393	4393	5393	6393	7393	8393	9393
remainder	7	6	5	4	3	2	1	0	10

The number $9393$ can no longer be changed, because the largest possible remainder modulo $11$ has already been reached ( $9393 \bmod 11 = 10$ ). This would be Justas's result.

However, this is not the best possible result. The best result is $9899$ , which can be reached, for example, with the following steps:

N	1399 → 1899 → 9899
remainder	2 → 7 → 10

Determine the largest number Justas can reach.

Input

A single line contains the two integers $N$ and $M$ .

Output

Output the largest number Justas can reach.

Constraints

$1 \le N < 10^{17}$
$1 \le M \le 10^9$

Examples3

Example 1
Input
```
1399 11
```
Expected output
```
9899
```
Example 2
Input
```
123 10
```
Expected output
```
129
```
Example 3
Input
```
89 7
```
Expected output
```
89
```