Збір ягід#9599

Збір ягід

1 секунда

128 мегабайтів

Середня

Бессі та її молодша сестра Елсі збирають ягоди в ягідному саду фермера Джона. У саду фермера Джона росте рівно $n$ ягідних дерев; дерево $i$ містить рівно $b_{i}$ b_i ягід. У Бессі є рівно $k$ кошиків. У кожен кошик можна покласти будь-яку кількість ягід з одного дерева, але не можна класти в один кошик ягоди з двох різних дерев, оскільки їхні смаки змішаються. Кошики можуть залишатися порожніми.

Бессі хоче максимізувати загальну кількість зібраних нею ягід. Однак фермер Джон хоче, щоб Бессі поділилася ягодами зі своєю молодшою сестрою. Тому Бессі повинна віддати Елсі $k /2$ кошиків, що містять найбільшу кількість ягід. Таким чином, Елсі може в результаті отримати більше ягід, ніж Бессі, що здається несправедливим, але, на жаль, стосунки між братами й сестрами не завжди бувають справедливими.

Допоможіть Бессі визначити максимальну кількість ягід, яку вона може зібрати.

Вхідні дані

У першому рядку знаходяться два цілих числа $n (1 \leq n \leq 1000)$ n~(1 \le n \le 1000) та $k (1 \leq k \leq 1000, k$ k~(1 \le k \le 1000, k — парне).

У другому рядку знаходяться $n$ цілих чисел $b_{1}, b_{2}, \dots, b_{n}$ b_1, b_2, \ldots, b_n ( $1 \leq b_{i} \leq 1000$ 1 \le b_i \le 1000).

Вихідні дані

Виведіть максимальну кількість ягід, яку може зібрати Бессі.

Приклади

Якщо Бессі заповнює

один кошик $6$ ягодами з дерева $2$ ;
два кошики, в кожен з яких кладе по $4$ ягоди з дерева $3$ ;
один кошик $4$ ягодами з дерева $4$ ;

то їй дістаються два кошики, в кожному з яких знаходиться по $4$ ягоди, і загалом вона отримує $8$ ягід.

Приклад 1