A16242. MEXanized Array

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.

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$ ).

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.

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]$ .