Berry Picking#9599
Bessie and her little sister Elsie are picking berries in Farmer John's berry patch. Farmer John's patch contains exactly berry trees; tree contains exactly b_i berries. Bessie has exactly baskets. Each basket can hold any number of berries from a single tree, but cannot contain berries from two different trees, as their flavors would clash. Baskets may be left empty.
Bessie wants to maximize the total number of berries she collects. However, Farmer John wants Bessie to share her berries with her little sister. Therefore, Bessie must give Elsie the baskets containing the largest numbers of berries. This means that Elsie may end up with more berries than Bessie, which seems unfair, but unfortunately, sibling dynamics are not always fair.
Help Bessie determine the maximum number of berries she can collect.
The first line contains two integers n~(1 \le n \le 1000) and k~(1 \le k \le 1000, k is even).
The second line contains integers b_1, b_2, \ldots, b_n (1 \le b_i \le 1000).
Print the maximum number of berries Bessie can collect.
If Bessie fills
one basket with berries from tree ;
two baskets, each containing berries from tree ;
one basket with berries from tree ;
then she receives the two baskets containing berries each, giving her berries in total.
Example 1