Let x₁, x₂,..., x_m be real numbers satisfying the following conditions:

a): − ${\frac{{1}}{{\sqrt{a}}}}$ $\le$ x_i $\le$ $\sqrt{{5}}$ ;
b): x₁ + x₂ +...+ x_m = b * $\sqrt{{a}}$ for some integers a and b (a > 0).

Determine the maximum value of x^p₁ + x^p₂ +...+ x^p_m for some even positive integer p.

Input

Each input line contains four integers: m, p, a, b ( m $\le$ 2000, p $\le$ 12, p is even). Input is correct, i.e. for each input numbers there exists x₁, x₂,..., x_m satisfying the given conditions.

Output

For each input line print one number - the maximum value of expression, given above. The answer must be rounded to the nearest integer.

Sample Input

1997 12 3 -318 
10 2 4 -1

Sample Output

189548 
6