More Cowbell

题意翻译

小图想要把他收藏的珍贵的 n 个牛铃搬到另一个地方去。出发前，他需要把牛铃打包进 k 个相同大小的盒子里，为了保证运输安全，同 1 个盒子里他不会放超过2个牛铃。由于小图需要尽量缩减开销，他希望知道能把所有牛铃打包好的盒子的最小尺寸。 小图是个非常细心的牛铃收藏家，他知道第 i (1 ≤ i ≤ n) 个牛铃的大小为整数 si ，并且，他已经把牛铃从小到大进行排序，（对于i > 1，si - 1 ≤ si ） 。小图同时也是一个打包小能手，只要牛铃的大小不超过盒子大小 s ，他可以把 1 个或者 2 个牛铃塞进大小刚好为 s 的盒子里。根据这些信息，请你帮助小图确定一个最小的盒子尺寸 s ，以便他能把所有的牛铃装进大小都为 s 的 k个盒子里。

题目描述

Kevin Sun wants to move his precious collection of $ n $ cowbells from Naperthrill to Exeter, where there is actually grass instead of corn. Before moving, he must pack his cowbells into $ k $ boxes of a fixed size. In order to keep his collection safe during transportation, he won't place more than two cowbells into a single box. Since Kevin wishes to minimize expenses, he is curious about the smallest size box he can use to pack his entire collection. Kevin is a meticulous cowbell collector and knows that the size of his $ i $ -th ( $ 1<=i<=n $ ) cowbell is an integer $ s_{i} $ . In fact, he keeps his cowbells sorted by size, so $ s_{i-1}<=s_{i} $ for any $ i&gt;1 $ . Also an expert packer, Kevin can fit one or two cowbells into a box of size $ s $ if and only if the sum of their sizes does not exceed $ s $ . Given this information, help Kevin determine the smallest $ s $ for which it is possible to put all of his cowbells into $ k $ boxes of size $ s $ .

输入输出格式

输入格式

The first line of the input contains two space-separated integers $ n $ and $ k $ ( $ 1<=n<=2·k<=100000 $ ), denoting the number of cowbells and the number of boxes, respectively. The next line contains $ n $ space-separated integers $ s_{1},s_{2},...,s_{n} $ ( $ 1<=s_{1}<=s_{2}<=...<=s_{n}<=1000000 $ ), the sizes of Kevin's cowbells. It is guaranteed that the sizes $ s_{i} $ are given in non-decreasing order.

输出格式

Print a single integer, the smallest $ s $ for which it is possible for Kevin to put all of his cowbells into $ k $ boxes of size $ s $ .

输入输出样例

输入样例 #1

2 1
2 5

输出样例 #1

7

输入样例 #2

4 3
2 3 5 9

输出样例 #2

9

输入样例 #3

3 2
3 5 7

输出样例 #3

8

说明

In the first sample, Kevin must pack his two cowbells into the same box. In the second sample, Kevin can pack together the following sets of cowbells: $ {2,3} $ , $ {5} $ and $ {9} $ . In the third sample, the optimal solution is $ {3,5} $ and $ {7} $ .