Ли наконец стал мастером на Codeforces, и потому решил сходить за подарками своим друзьям. Он приобрел \(n\) целых чисел, и теперь настало время распределить их между друзьями...
У Ли есть \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) в своем рюкзаке, а также у него \(k\) друзей. Ли хочет распределить все целые числа из рюкзака между друзьями так, чтобы \(i\)-му другу досталось ровно \(w_i\) чисел и каждое число досталось ровно одному другу.
Назовем уровнем счастья друга сумму максимального и минимального числа, которое он получит.
Ли хочет сделать друзей как можно более счастливыми, другими словами, он хочет максимизировать суммарный уровень счастья друзей. Конечно же, Ли просит вас помочь ему посчитать этот максимальный суммарный уровень счастья.
Выходные данные
Для каждого набора входных данных выведите по одному числу — максимальный суммарный уровень счастья, который сможет достигнуть Ли.
Примечание
В первом наборе входных данных, Ли нужно отдать наибольшее число первому другу (его уровень счастья будет равен \(17 + 17\)) и остальные числа — второму (его уровень счастья будет равен \(13 + 1\)).
В втором наборе, Ли нужно отдать \(\{10, 10, 11\}\) и первому и второму другу, тогда суммарный уровень счастья будет равен \((11 + 10) + (11 + 10)\)
В третьем наборе, у Ли четыре друга и четыре числа. Не важно, как он распределит числа между ними.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4 2
1 13 7 17
1 3
6 2
10 10 10 10 11 11
3 3
4 4
1000000000 1000000000 1000000000 1000000000
1 1 1 1
|
48
42
8000000000
|