eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Сбор ягод

Сбор ягод

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Бесси и её маленькая сестра Эльза собирают ягоды в саду Фермера Джона. В саду ФД имеется ровно n деревьев с ягодами. На дереве i висит ровно b_i ягод. У Бесси имеется ровно k корзин. Каждая корзина может содержать любое количество ягод с одного дерева, но не может содержать ягоды с двух различных деревьев (поскольку вкусы ягод отрицательно влияют друг на друга). Корзины могут оставаться пустыми.

Бесси хочет максимизировать количество ягод, которое она соберёт. Однако ФД хочет, чтобы Бесси поделилась ягодами со своей младшей сестрой, поэтому Бесси должна отдать Эльзе k / 2 корзин с наибольшим количеством ягод. Это значит, что у Эльзы может даже оказаться больше ягод чем у Бесси.

Помогите Бесси вычислить максимальное количество ягод, которое она может получить после дележа.

Входные данные

Первая строка содержит два целых числа 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).

Выходные данные

Выведите максимальное количество ягод, которое Бесси может получить после дележа.

Пример

Входные данные #1
5 4
3 6 8 4 2
Выходные данные #1
8

Примечание

Если Бесси заполнит:

  • одну корзину 6 ягодами с дерева \:2

  • две корзины по 4 ягоды с дерева \:3

  • одну корзину 4 ягодами с дерева \:4

Тогда она получит две корзины по 4 ягоды, что даст в сумме 8 ягод.

Источник 2020 USACO Январь, Серебро