Problem D
Jamboree
A group of scouts are preparing to go to a large meeting with other scouts. Their leader Hildeborg, in spirit of the scout motto “be prepared”, wants to distribute some useful items among the scouts that they most probably will need on their adventure. The items come in different sizes, so to make this as fair as possible, she wants to make sure that the total size of items carried by any scout is as small as possible. Furthermore, Hildeborg does not want to give more than two items to any scout as she is afraid that it otherwise will be too hard for them to remember to bring everything. Given the sizes of the items, what is the least maximum total size, computed as the sum of items, any scout will have to carry?
Input
The first line of input contains two positive integers $N$ and $M$ ($1 \leq N \leq 2M$, $1 \leq M \leq 100$). $N$ is the number of useful items, and $M$ is the number of scouts. The second line contains $N$ positive integers $a_ i$ ($1 \leq a_ i\leq 10^7$) giving the sizes of the items.
Output
Print one integer, the smallest total size that any scout has to carry.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 4 10 10 10 |
10 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 4 9 12 3 9 10 |
12 |
