题目描述

蒙青创要开始集训了，这次是$ICPC$赛制，一共有$k$个队员，他们要共同完成$n$道题目，$tyk$需要将这个题目分成 $k$ 个非空的连续子数组交给不同的队员完成，$tyk$想要使得这 k 个子数组各自和的最大值 最小。这样的话，大家就可以早点出去玩啦！

返回分割后最小的和的最大值。

子数组 是数组中连续的部份。

输入格式

一共两行，第一行两个数$n$和$k$，表示一个有多少题和多少队员

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，代表每个题需要的时间。

输出格式

输出分割后最小的和的最大值。

样例

5 2
7 2 5 10 8

18

一共2个队员，第一个负责前3题，花费14，第2名队员完成4,5题，花费18，所以答案是18

数据范围

对于每个测试点，$1 \leq n\leq 10^6$，$1\leq a_1,a_2,\dots,a_n \leq 10^5$。