A. МЕХанизированный массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны три целых неотрицательных числа $$$n$$$, $$$k$$$ и $$$x$$$. Найдите максимальную возможную сумму элементов массива, состоящего из целых неотрицательных чисел, который состоит из $$$n$$$ элементов, его MEX равен $$$k$$$, и все его элементы не превосходят $$$x$$$. Если такого массива не существует, то выведите $$$-1$$$.

MEX (minimum excluded, минимальное отсутствующее) массива — это наименьшее целое неотрицательное целое число, которое не принадлежит массиву. Например:

  • MEX массива $$$[2,2,1]$$$ равен $$$0$$$, потому что $$$0$$$ не принадлежит массиву.
  • MEX массива $$$[3,1,0,1]$$$ равен $$$2$$$, потому что $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ — нет.
  • MEX массива $$$[0,3,1,2]$$$ равен $$$4$$$, потому что $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ принадлежат массиву, а $$$4$$$ — нет.
Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$x$$$ ($$$1 \leq n, k, x \leq 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]$$$.