Berry Picking

Bessie and her sister Elsie are picking berries in Farmer John's berry patch. The patch contains \(N\) berry trees (\(1\le N\le 1000\)); tree \(i\) contains \(B_i\) berries (\(1\le B_i\le 1000\)). Bessie has \(K\) baskets (\(1\le K\le 1000\), and \(K\) is even). Each basket may hold any number of berries that are picked from a single tree; however, berries from different trees cannot be mixed in a basket. It is allowed for a basket to remain empty.

Bessie wants to maximize the total number of berries she ends up with. However, Farmer John requires that Bessie share with Elsie by giving her the \(\frac{K}{2}\) baskets that contain the largest number of berries. As a result, Elsie may end up with more berries than Bessie.

Help Bessie determine the maximum number of berries she can collect.

inputFormat

The first line contains two integers (N) and (K) separated by a space. The second line contains (N) integers (B_1, B_2, \dots, B_N) representing the number of berries on each tree.

outputFormat

Output a single integer representing the maximum number of berries that Bessie can keep.

sample

5 4
3 6 8 4 2

7