UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1851. Pku2759 Distributing tasks

Statistics 下载数据

Description

Jiajia,Wind和一群朋友去郊外植树。他们认为树和人一样,都应该是一对一对的。因此他们想种偶数棵树,并且这偶数棵树排列成2*n的形状。现在Jiajia已经选定了种树的位置,并且根据土壤的硬度给每个位置打了一个难度分。Wind决定把种树的工作分成若干部分,每个人负责一部分。每一部分工作都要种一个矩形内的树木,难度就是种这些树木的难度分之和。Jiajia一行共有m个人,他希望工作能尽量分的均匀,也就是希望分配给每个人的工作中难度最大的最小。 下图即为样例,不同的颜色代表不同部分的植树工作。

Input

输入文件第一行是n和m。此后两行,每行n个正整数从左到右描述每个位置的种树难度分。 你可以认为n<=10000,m<=min{2*n,1000},同时所有种树难度分之和不超过2^30。

Output

输出文件仅包含一个整数,为最优方案中最大的工作难度。

Sample Input

3 3
1 2 6
2 1 6

Sample Output

6

Hint

Source