Time Limit: 1000 ms   Case Time Limit: 1000 ms   Memory Limit: 64 MB

Total Submission: 53   Submission Accepted: 22

Description

众所周知，“西瓜”是大名鼎鼎的江洋大盗。有一次他偷到了一批宝库。

这批宝物共有n个，他一共有k个箱子。他只能用这些箱子把这些宝物运出去，为了保证运输安全，他不会把两个以上的宝物装入同一个箱子（一个箱子只能装1个或者2个宝物）。这些宝物的大小分别是s(1)、s(2)、s(3)……s(n)。（题目给出的重量保证是非降序，即s(i-1)<=s(i) 对于任何i>1)。

装进宝物后，每个箱子的容量要大于或者等于所装的宝物大小之和。为了规格统一，这些箱子每个的容量要一致。为了降低运费，箱子的容量要尽可能小。“西瓜”想要知道，在能运走的情况下，箱子容量最小是多少。

 

Input

多组输入

先输入n和k (1≤n≤2·k≤100 000)，n是宝物数量，k是箱子数量。

下一行输入空格分隔的n个整数, s1,s2,...,sn (1≤s1≤s2≤...≤sn≤1 000 000),代表这些宝物的重量。

 

Output

输出一个整数，代表这些箱子容量的最小值。

 

Sample Input

Original

Transformed

4 32 3 5 9

 

Sample Output

Original

Transformed

9

 

 只需将宝物按照从大到小装箱，然后再将剩下的宝物按照从大到小装入从小到大的箱子中

最后求出所有箱子中最大值即可

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include