Description

In mathematics, a Diophantine equation is a multivariable linear equation (多元一次方程式) whose solutions must be integers.  The solutions of a nonnegative Diophantine equation must be nonnegative integers.

 

For example, a nonnegative Diophantine equation is 7x+4y+z=20 and its solutions are (0, 0, 20), (0, 1, 16), (0, 2, 12), (0, 3, 8), (0, 4, 4), (0, 5, 0), (1, 0, 13), (1, 1, 9), (1, 2, 5), (1, 3, 1), (2, 0, 6) and (2, 1, 2).

 

Now, for a given nonnegative Diophantine equation, you need to output the minimum of the sums of solutions. For example, the minimum sum of above nonnegative Diophantine equation is 5 which comes from (0, 5, 0), (1, 3, 1) or (2, 1, 2).

Input

The input contains three lines. The first line has an integer N (0a nonnegative Diophantine equation.  The final line has an integer, which is the right hand side of the Diophantine equation.  The given nonnegative Diophantine equation has at least one solution.

Output

Output the minimum sum of the solutions for a nonnegative Diophantine equation. There is a newline at the end of output.

Sample Input  Download

Sample Output  Download

Tags

Discuss