問題文

$N(N$は奇数$)$ 人の人間がテストを受け、それぞれ $0$ 点以上 $P$ 点以下の整数得点を獲得しました。
あなたはテスト結果について $N$ 人の得点の中央値が $X$ 点、最頻値が $Y$ 点という情報を得ました。情報に合致する $N$ 人の得点が存在するならそのような $N$ 人の得点の総和として考えられる最大値を求めてください。存在しないならそのことを報告してください。

中央値とは $N$ 人の得点を昇順ソートしたときに1-indexedで前から $\frac{N + 1}{2}$ 個目の値のことです。
最頻値はその得点を取った人数が一番多い得点のことです。但しこの問題においてはそのような得点が複数ある場合それらの平均を最頻値とします。

一つのテストデータでちょうど $10$ 個のケースが与えられるので全てについて解いてください。

注意

この問題の実行時間制限は $4$ 秒です。
writer解は C++14 : 920 ms, Java11 : 1703 ms, PyPy3 : 3994 ms でACしています。

入力

$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}$

入力は全て整数
$1 \le i \le 10$ のとき :
 $1 \le N_i \lt 1000$
 $N_i$ は奇数
 $1 \le P_i \le 10^9$
 $0 \le X_i \le P_i$
 $0 \le Y_i \le P_i$

出力

$10$ 行に渡って、$i$ 行目では $N = N_i, P = P_i, X = X_i, Y = Y_i$ としたときの情報に合致する $N$ 人の得点の総和として考えられる最大の値を出力してください。
但し、情報に合致するテスト結果が存在しないならばその行は-1を出力してください。

サンプル

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