The Strange Sequence

Time limit1sMemory limit128 MB

Summary

Given a start value and index n, build the sequence where each next term is the smallest number greater than the previous one whose digit sum equals the digit sum of four times the previous term, then print the n-th term.

Level: Medium6 of 10
Topics: Implementation, Math, Greedy, Simulation
Solved: No attempts yet

Problem

Consider a sequence of positive integers $a_1, a_2, a_3, \dots$ . The first term $a_1$ is given. For every $i > 1$ , the term $a_i$ is the smallest integer that satisfies both of the following conditions:

$a_i > a_{i-1}$ ;
the digit sum of $a_i$ equals the digit sum of $4 \cdot a_{i-1}$ .

Given the first term $a_1$ and an index $n$ , output the value of $a_n$ .

Input

A single line contains two integers $a_1$ and $n$ separated by a space ( $0 < a_1 < 20$ , $0 < n < 10000$ ).

Output

Print a single integer: the value of $a_n$ . All test data are chosen so that $a_n$ does not exceed $10^9$ .

Examples1

Example 1
Input
```
4 5
```
Expected output
```
79
```