给你三个非负整数 $$$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$$$) — 测试用例的数量。然后是测试用例的描述。
每个测试用例的唯一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$x$$$ ($$$1 \leq n, k, x \leq 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
注意
在第一个测试用例中,最大和为 $$$7$$$,其中一个有效数组为 $$$[0, 1, 2, 2, 2]$$$。
在第二个测试用例中,没有长度为 $$$n$$$ 的有效数组。
在第三个测试用例中,最大总和为 $$$57$$$,有效数组之一为 $$$[0, 1, 28, 28]$$$。