题目描述

给定三个非负整数 $n$、$k$ 和 $x$。请你构造一个由非负整数组成的长度为 $n$ 的数组，使其 MEX 等于 $k$，且所有元素都不超过 $x$，并求该数组元素和的最大值。如果不存在这样的数组，输出 $-1$。

MEX（minimum excluded）指的是数组中没有出现的最小非负整数。例如：

• $[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$），表示测试用例的数量。接下来每个测试用例包含一行，包含三个整数 $n$、$k$ 和 $x$（$1 \leq n, k, x \leq 200$）。

输出格式

对于每个测试用例，输出一个整数，表示满足条件的数组元素和的最大值。如果不存在这样的数组，输出 $-1$。

说明/提示

在第一个测试用例中，最大和为 $7$，其中一个合法的数组为 $[0, 1, 2, 2, 2]$。

在第二个测试用例中，不存在长度为 $n$ 的合法数组。

在第三个测试用例中，最大和为 $57$，其中一个合法的数组为 $[0, 1, 28, 28]$。

由 ChatGPT 4.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

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