Однажды, люди, эльфы, гномы и другие жители Средиземья собрались отнять у Смога украденные у них сокровища. Во имя этой великой цели они сплотились вокруг сильного эльфа Тимофея и начали планировать свержение правителя Одинокой горы.
Армия жителей Средиземья будет состоять из нескольких отрядов. Известно, что каждая пара существ одной расы, которые находятся в разных отрядах, прибавляет \(b\) единиц к суммарной силе армии. Но так как Тимофею будет сложно руководить армией, состоящей из большого числа отрядов, то суммарная сила армии, состоящей из \(k\) отрядов, уменьшается на \((k - 1) \cdot x\) единиц. Обратите внимание, что армия всегда состоит из хотя бы одного отряда.
Известно, что в Средиземье проживают \(n\) рас, и количество существ \(i\)-й расы равно \(c_i\). Помогите жителям Средиземья определить максимальную силу армии, которую они могут составить.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную силу армии, которую могут составить жители Средиземья.
Примечание
В первом наборе входных данных жители Средиземья могут составить \(3\) отряда. Так как \(x = 0\), то сила армии не уменьшится из-за количества отрядов. Жителей по отрядам можно распределить так:
- Единственного представителя первой расы можно отправить в первый отряд.
- Первого представителя второй расы можно отправить в первый отряд, второго представителя второй расы можно отправить во второй отряд. Тогда суммарная сила армии увеличится на \(b = 1\).
- Первого представителя третьей расы можно отправить в первый отряд, второго представителя третьей расы можно отправить во второй отряд, третьего представителя третьей расы можно отправить в третий отряд. Тогда суммарная сила армии увеличится на \(3 \cdot b = 3\), так как они образуют три пары, находящиеся в разных отрядах.
Таким образом, суммарная сила армии равна \(4\).
Во втором наборе входных данных жители Средиземья могут составить \(3\) отряда. Так как \(x = 10\), то сила армии уменьшится на \(20\). Жителей по отрядам можно распределить так:
- Первого представителя первой расы можно отправить в первый отряд, второго представителя первой расы можно отправить во второй отряд. Тогда суммарная сила армии увеличится на \(b = 5\).
- Первого и второго представителя второй расы можно отправить в первый отряд, третьего и четвёртого представителя второй расы можно отправить во второй отряд, пятого представителя третьей расы можно отправить в третий отряд. Тогда суммарная сила армии увеличится на \(8 \cdot b = 40\).
- Первого представителя третьей расы можно отправить в первый отряд, второго представителя третьей расы можно отправить во второй отряд, третьего представителя третьей расы можно отправить в третий отряд. Тогда суммарная сила армии увеличится на \(3 \cdot b = 15\), так как они образуют три пары, находящиеся в разных отрядах.
Таким образом, суммарная сила армии равна \(5 + 40 + 15 - 20 = 40\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 1 0
1 2 3
3 5 10
2 5 3
4 3 3
3 2 1 2
4 1 0
4 1 4 2
4 1 10
4 1 4 2
|
4
40
9
13
0
|