营救

题目描述

一座摩天大楼起了大火，n 个人都被困在了顶层狭长的走廊上，大家排满长长的队伍等着逃离险境。但火势很猛，消防员升起的救生舱只有 m 次运人下来的机会，并且每次运的人的总重量还不能太重，避免将救生舱压垮。

此时如何将这一排人分隔成 m 个连续的小组（大家遵守逃生守则，没有人会往前插队），并且让这 m 个组中总重量最重的那个组的重量尽量小？这样才能快速安全地将大家都救离险境。

现在告诉你这 n 个人的体重，请你找出一种分组方法，让这 m 个组中总重量最重的那个组的重量尽量小，并输出这个组的总重量。

输入描述

第一行两个正整数 n 和 m，中间用一个空格隔开，表示有 n 个逃生的人和要分隔成 m 个连续的小组。

第二行 n 个正整数 $a_i$，每个整数之间用一个空格隔开，表示 n 个人的体重。

输出描述

一个正整数，表示 m 个组中总重量最重的那个组的重量。

样例

输入：

6 3
20 30 50 80 100 120

输出：

180

样例解释：一种合理的分法是 (20 30 50) (80 100) (120)。

输入样例 #2

1 1
1

输出样例 #2

1

输入样例 #3

1 1
200

输出样例 #3

200

数据范围

原图列出：1 ≤ n ≤ 10000；100 ≤ m ≤ 1000；1 ≤ $a_i$ ≤ 200。原图样例中 m = 3，与“100 ≤ m”不一致，保留原图数据规范，实际测试应以有解的分组为准。