An array of integers A[i] (i > 1) is defined in the following way: an element A[k] ( k > 1) is the smallest number greater than A[k-1] such that the sum of its digits is equal to the sum of the digits of the number 4* A[k-1] .

You need to write a program that calculates the N th number in this array based on the given first element A[1] .

INPUT: In one line of standard input there are two numbers seperated with a single space: A[1] (1 <= A[1] <= 100) and N (1 <= N <= 10000).

OUTPUT: The standard output should only contain a single integer A[N] , the Nth number of the defined sequence.

Input: 7 4

Output: 79

Explanation: Elements of the array are as follows: 7, 19, 49, 79... and the 4th element is solution.

I tried solving this by coding a separate function that for a given number A[k] calculates the sum of it's digits and finds the smallest number greater than A[k-1] as it says in the problem, but with no success. The first testing failed because of a memory limit, the second testing failed because of a time limit, and now i don't have any possible idea how to solve this. One friend suggested recursion, but i don't know how to set that.

Anyone who can help me in any way please write, also suggest some ideas about using recursion/DP for solving this problem. Thanks.