Məsələlər
Сбор ягод
Сбор ягод
Бесси и её маленькая сестра Эльза собирают ягоды в саду Фермера Джона. В саду ФД имеется ровно $n$ деревьев с ягодами. На дереве $i$ висит ровно $b_i$ ягод. У Бесси имеется ровно $k$ корзин. Каждая корзина может содержать любое количество ягод с одного дерева, но не может содержать ягоды с двух различных деревьев (поскольку вкусы ягод отрицательно влияют друг на друга). Корзины могут оставаться пустыми.
Бесси хочет максимизировать количество ягод, которое она соберёт. Однако ФД хочет, чтобы Бесси поделилась ягодами со своей младшей сестрой, поэтому Бесси должна отдать Эльзе $k / 2$ корзин с наибольшим количеством ягод. Это значит, что у Эльзы может даже оказаться больше ягод чем у Бесси.
Помогите Бесси вычислить максимальное количество ягод, которое она может получить после дележа.
\InputFile
Первая строка содержит два целых числа $n\:(1 \le n \le 1000)$ и $k\:$($1 \le k \le 1000, k$ чётное). Вторая строка содержит $n$ целых чисел $b_1, b_2, ..., b_n\:(1 \le b_i \le 1000)$.
\OutputFile
Выведите максимальное количество ягод, которое Бесси может получить после дележа.
\Note
Если Бесси заполнит:
\begin{itemize}
\item одну корзину $6$ ягодами с дерева $\:2$
\item две корзины по $4$ ягоды с дерева $\:3$
\item одну корзину $4$ ягодами с дерева $\:4$
\end{itemize}
Тогда она получит две корзины по $4$ ягоды, что даст в сумме $8$ ягод.
Giriş verilənləri #1
5 4 3 6 8 4 2
Çıxış verilənləri #1
8