Даны m = n·k деревянных досок. i-я доска имеет длину ai. Необходимо собрать n бочек, каждая из k досок, для сборки можно использовать любые k досок. Каждая доска должна принадлежать ровно одной бочке.
Объемом vj бочки j назовем длину минимальной доски в ней.
Вы хотите собрать ровно n бочек с максимальным суммарным объемом. Однако их требуется сделать достаточно схожими, разница между объемами любых двух полученных бочек не должна превосходить l, это значит, что |vx - vy| ≤ l для любых 1 ≤ x ≤ n и 1 ≤ y ≤ n.
Выведите максимальную возможную сумму объемов достаточно схожих бочек или 0, если невозможно удовлетворить условие.
Выходные данные
Выведите одно целое число — максимальную сумму объемов бочек или 0, если невозможно собрать ровно n бочек, удовлетворяющих условию |vx - vy| ≤ l для любых 1 ≤ x ≤ n и 1 ≤ y ≤ n.
Примечание
В первом примере можно собрать следующие бочки: [1, 2], [2, 2], [2, 3], [2, 3].
В втором примере можно собрать следующие бочки: [10], [10].
В третьем примере можно собрать следующие бочки: [2, 5].
В четвертом примере разница между объемами бочек в любом разделении кк минимум 2, так что невозможно сделать бочки достаточно схожими.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2 1
2 2 1 2 3 2 2 3
|
7
|
|
2
|
2 1 0
10 10
|
20
|
|
3
|
1 2 1
5 2
|
2
|
|
4
|
3 2 1
1 2 3 4 5 6
|
0
|