1886: NEEDY GIRL OVERDOSE

糖糖在某次下播后，又该吃药了。虽然这个药物能治疗她的疾病，但是具有比较大的副作用。于是糖糖决定，把药物按次数分成若干次吃。具体如下：

设药物有n片，按剂量分成a1,a2,a3...an毫克。糖糖需要用k次来把这n片药物吃完。即：将a按原顺序分成连续的k段（每一段均不为空，要是空了糖糖还吃什么呀）。假如药物剂量为为4 2 4 5 1，需要三次吃完，可选择的方案有：[4 2][4 5][1]，   [4][2 4][5 1]，[4 2 4][5][1]等等。

为了保证副作用带来的伤害最低并且药效最好，糖糖让阿p你来帮助她分药，要求，分成的k段中，每段药物剂量和的最大值最小，比如：4 2 4 5 1中，要求分成三次吃完，若分成[4 2][4 5][1]，最大值为4+5=9；若分成 [4][2 4][5 1]，最大值为2+4或者5+1=6；并且，其他任何分段方案的最大值，没有比6更小的，故对于4 2 4 5 1，每段药物剂量和的最大值最小为6。

作为她的男朋友，请你帮帮糖糖。

第一行两个整数n和k，代表药物总片数和要求分的次数（段数），1<=n<=100000,1<=k<=n。

第二行n个整数ai,代表每片的剂量，1<=ai<100000000）。

保证答案不会超过1000000000。

5 3
4 2 4 5 1

6