e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

2020 USACO January Silver

Сбор ягод

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

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

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

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

Первая строка содержит два целых числа n (1n1000) и k ( 1k1000, k чётное). Вторая строка содержит n разделённых пробелами целых чисел b1, b2, ... , bn (1bi1000).

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

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

Пример

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

  • одну корзину 6 ягодами с дерева 2
  • две корзины по 4 ягоды с дерева 3
  • одну корзину 4 ягодами с дерева 4

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
5 4
3 6 8 4 2
Вихідні дані #1
8
Джерело 2020 USACO January Silver