Minimum Storage Capacity

Assign all games to exactly k children; each child gets at least one and at most two games, and each game goes to only one child. Every child has the same storage capacity. Find the minimum capacity that makes the assignment possible, that is, minimize the maximum total size of the games any child receives.

输入格式

The first line contains n k and the second line contains the game sizes. This site adds 1≤n,k≤200000, 1≤size[i]≤10^9. Unsolvable inputs are not excluded, and this site specifies the output −1 when there is no solution.

输出格式

Output a single integer, the answer.

样例 1

输入：

4 3
9 2 4 6

输出：

9

样例 2

输入：

4 2
8 3 5 4

输出：

11

样例 3

输入：

3 1
1 2 3

输出：

-1

样例说明

The answers are 9, 11 and −1. In the first example 2 and 4 form one group, and 6 and 9 each form a group of their own; pairing the largest game 9 is not optimal. Source 304 contains a placeholder loop that never terminates, and 305 also pairs the large games incorrectly; this site's code is original.