Problem Statement

$N(N$ is odd$)$ people took a test, and each of them obtained an integer score between $0$ and $P$ points, inclusive.
You have learned about the test results that the median of the $N$ scores is $X$ points and the mode is $Y$ points. If there exist $N$ scores consistent with this information, find the maximum possible sum of such $N$ scores. If none exist, report that fact.

The median is the value at the $\frac{N + 1}{2}$-th position from the front (1-indexed) when the $N$ scores are sorted in ascending order.
The mode is the score obtained by the largest number of people. However, in this problem, if there are multiple such scores, their average is regarded as the mode.

Each test file contains exactly $10$ cases. Solve all of them.

Notes

The execution time limit for this problem is $4$ seconds.
The writer's solutions got AC with C++14 : 920 ms, Java11 : 1703 ms, PyPy3 : 3994 ms.

Input

$N_1\ P_1\ X_1\ Y_1$
$N_2\ P_2\ X_2\ Y_2$
$N_3\ P_3\ X_3\ Y_3$
$\hspace{25pt} \vdots$
$N_{10}\ P_{10}\ X_{10}\ Y_{10}$

All inputs are integers.
For $1 \le i \le 10$ :
$1 \le N_i \lt 1000$
$N_i$ is odd
$1 \le P_i \le 10^9$
$0 \le X_i \le P_i$
$0 \le Y_i \le P_i$

Output

Output $10$ lines. On the $i$-th line, output the maximum possible sum of $N$ scores consistent with the information when $N = N_i, P = P_i, X = X_i, Y = Y_i$.
However, if no test result is consistent with the information, output -1 on that line.

Sample

5 100 80 80
5 100 70 80
5 100 100 0
7 100 7 53
17 100 69 92
11 100 27 55
1 100 50 50
101 100 71 68
999 1000000000 500000000 500000001
999 1000000000 500000001 500000000

440
400
-1
325
1379
650
50
8518
747999877246
749000000000

3 100 0 0
3 100 30 31
3 100 30 53
3 100 30 54
3 100 50 50
3 100 100 100
17 8 1 3
19 19 8 11
19 17 2 7
19 9 2 9

100
93
159
-1
200
300
59
241
148
99