Беси и её маленькая сестра Эльза собирают ягоды в саду Фермера Джона.
В саду ФД имеется ровно \(N\) деревьев с ягодами (\(1\le N\le 1000\));
На дереве \(i\) висит ровно \(B_i\) ягод (\(1\le B_i\le 1000\)). У Беси
есть ровно \(K\) корзин (\(1 \le K \le 1000\), \(K\) - чётное).
Каждая корзина может содержать сколько Беси хочет ягод с одного дерева,
но не может содержать ягоды с двух различных деревьев (поскольку вкусы
ягод отрицательно влияют друг на друга). Корзины могут оставаться
пустыми.
Беси хочет максимизировать количество ягод, которое она соберёт.
Однако ФД хочет, чтоб Беси поделилась ягодами со своей младшей сестрой,
поэтому Беси должна отдать Эльзе \(K/2\) корзин с наибольшим количеством ягод.
Это значит, что у Эльзы может даже оказаться больше ягод чем у Беси.
Помогите Беси вычислить максимальное количество ягод, которое она может
получить после делёжки.
SCORING:
- Тесты 1-4 удовлетворяют условию \(K\le 10.\)
- Тесты 5-11 не имеют дополнительных ограничений.
ФОРМАТ ВВОДА (файл berries.in):
Первая строка ввода содержит два разделённых пробелом целых числа
\(N\) и
\(K\).
Вторая строка содержит \(N\) разделённых одиночными пробелами целых чисел
\(B_1,B_2,\ldots,B_N.\)
ФОРМАТ ВЫВОДА (файл berries.out):
Одна строка с ответом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
3 6 8 4 2
|
8
|