You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给出 $N$ 和 $M$， 然后给出 $N$个数 $a_i$。

把 $N$ 个数分成 $M$ 组（只能连续分），使得每次分完后，以产生的 $M$ 组数中的和最大的为标准，通过不同的分组方案，找到这些最大值中最小的那个。

输出这个最小值。

输入格式

第一行：$N$ 和 $M$。

第二行到第 $N+1$ 行：每行一个数 $a_i$，表示给出的 $N$ 个数。

输出格式

输出这个最小值。

样例

7 5
100
400
300
100
500
101
400

500

样例解释

$100,400$ 一组，$300,100$ 一组，$500$ 一组，$101$ 一组，$400$ 一组。

数据范围

$1\le M\le N\le10^5,1\le a_i\le10^4$。