← 返回题目列表

Codeforces · 1870/A

A. MEXanized 数组

中文机器翻译题面 查看原题

给你三个非负整数 $$$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]$$$。