Problem Description

Bessie and her sister Elsie are picking berries in Farmer John's berry orchard. There are $N$ berry trees in the orchard ($1 \leq N \leq 1000$). Tree $i$ has $B_i$ berries ($1 \leq B_i \leq 1000$). Bessie has $K$ baskets ($1 \leq K \leq 1000$, and $K$ is even). Each basket can hold any number of berries picked from the same tree, but it cannot contain berries from different trees, because they may taste different. A basket may also be left empty.

Bessie wants to maximize the number of berries she gets. However, Farmer John wants Bessie to share with her sister, so Bessie must give the $K/2$ baskets with more berries to Elsie. This means Elsie may end up with more berries than Bessie, which is unfair, but that is often how sisters are.

Help Bessie find the maximum number of berries she can get.

Input Format

The first line contains the space-separated integers $N$ and $K$.

The second line contains $N$ space-separated integers $B_1,B_2,\ldots,B_N$.

Output Format

Output one line with the answer.

5 4
3 6 8 4 2

8

Hint

Sample Explanation

If Bessie puts:

• 6 berries from tree 2 into one basket,
• 4 berries from tree 3 into each of two baskets,
• 4 berries from tree 4 into one basket,

then she can get two baskets with 4 berries each, for a total of 8 berries.

Subtasks

• Test cases $1 \sim 4$ satisfy $K \leq 10$.
• Test cases $5 \sim 11$ have no additional constraints.

Translated by ChatGPT 5