Вам даны три целых неотрицательных числа \(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\) — нет.
Выходные данные
На каждый набор входных данных выведите одно число — максимальную сумму элементов подходящего массива, или \(-1\), если такого массива не существует.
Примечание
В первом наборе входных данных максимальная сумма равна \(7\), один из подходящих массивов — это \([0, 1, 2, 2, 2]\).
Во втором наборе входных данных не существует подходящих массивов длины \(n\).
В третьем наборе входных данных максимальная сумма равна \(57\), один из подходящих массивов — это \([0, 1, 28, 28]\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|