310684: CF1870A. MEXanized Array

A. MEXanized Arraytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given three non-negative integers $n$, $k$, and $x$. Find the maximum possible sum of elements in an array consisting of non-negative integers, which has $n$ elements, its MEX is equal to $k$, and all its elements do not exceed $x$. If such an array does not exist, output $-1$.

The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:

• The MEX of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
• The MEX of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
• The MEX of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. Then follows the description of the test cases.

The only line of each test case contains three integers $n$, $k$, and $x$ ($1 \leq n, k, x \leq 200$).

Output

For each test case, output a single number — the maximum sum of elements in a valid array, or $-1$, if such an array does not exist.

ExampleInput

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

Output

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

Note

In the first test case, the maximum sum is $7$, and one of the valid arrays is $[0, 1, 2, 2, 2]$.

In the second test case, there are no valid arrays of length $n$.

In the third test case, the maximum sum is $57$, and one of the valid arrays is $[0, 1, 28, 28]$.

题目大意：
题目名为 "MEXanized Array"，给定三个非负整数 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 ≤ t ≤ 1000)，表示测试用例的数量。
- 接下来的每行包含三个整数 n、k 和 x (1 ≤ n, k, x ≤ 200)，描述一个测试用例。

输出：
- 对于每个测试用例，输出一个数字，表示有效数组的元素最大和，或者如果这样的数组不存在，则输出 -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
```

注意：
- 在第一个测试用例中，最大和为 7，一个有效的数组是 [0, 1, 2, 2, 2]。
- 在第二个测试用例中，不存在长度为 n 的有效数组。
- 在第三个测试用例中，最大和为 57，一个有效的数组是 [0, 1, 28, 28]。题目大意： 题目名为 "MEXanized Array"，给定三个非负整数 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 ≤ t ≤ 1000)，表示测试用例的数量。 - 接下来的每行包含三个整数 n、k 和 x (1 ≤ n, k, x ≤ 200)，描述一个测试用例。 输出： - 对于每个测试用例，输出一个数字，表示有效数组的元素最大和，或者如果这样的数组不存在，则输出 -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 ``` 注意： - 在第一个测试用例中，最大和为 7，一个有效的数组是 [0, 1, 2, 2, 2]。 - 在第二个测试用例中，不存在长度为 n 的有效数组。 - 在第三个测试用例中，最大和为 57，一个有效的数组是 [0, 1, 28, 28]。