题目描述

已知三个非负整数 $n$、$k$ 和 $x$。在一个包含 $n$ 个元素、MEX 等于 $k$ 且所有元素都不超过 $x$ 的非负整数数组中，求出元素的最大可能和。

如果这样的数组不存在，则输出 -1。

数组的 MEX（最小排除值） 是不属于该数组的最小非负整数。例如：

• [2, 2, 1] 的 MEX 为 0，因为 0 不属于数组；
• [3, 1, 0, 1] 的 MEX 为 2，因为 0 和 1 属于数组，但 2 不属于数组；
• [0, 3, 1, 2] 的 MEX 是 4，因为 0, 1, 2, 3 都属于数组，但 4 不属于数组。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——测试用例的数量。
接下来是 $t$ 个测试用例，每个测试用例占一行，包含三个整数 $n$, $k$, 和 $x$（$1 < n, k, x < 200$）。

输出格式

对于每个测试用例，输出一个整数——满足条件的数组的最大可能和。如果不存在这样的数组，则输出 -1。

输入样例 #1

9
5 3 3
4 7 5
4 2 28
12 10 6
57 51 122
200 1 200
2 2 1
3 2 1
4 7 10

输出样例 #1

7
-1
57
-1
2007
39800
1
2
-1

题目说明

以第一个测试用例为例：

• $n = 5$, $k = 3$, $x = 3$
• 由于数组 MEX 必须为 3，数组中必须包含数值 {0,1,2}，且不能包含数值 3。
• 所以至少需要 3 个数来覆盖 0, 1, 2。如果 $x > 3$，我们可以重复使用 x 来尽可能增大总和。
• 一个可行数组为 [0, 1, 2, 2, 2]，总和为 7。 在第二个测试用例中，没有长度为n的有效数组。 在第三个测试用例中，最大和为57，其中一个有效数组为[0,1,28,28]。