题目描述

一座摩天大楼起了大火，n个人都被困在了顶层狭长的走廊上，大家排着长长的队伍等着逃离险境。但火势很猛，消防员升起的救生舱只有m次运人下来的机会，并且每次运的人总重量还不能太重，避免将救生舱压垮。此时如何将这一排人分隔成m个连续的小组，（大家遵守逃生守则，没有人会往前插队），并且让这m个组中总重量最重的那个组的重量尽量小。这样才能快速安全的将大家都救离险境。

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

输入

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

第二行n个正整数，每个整数之间用一个空格隔开，表示n个人的体重(单位:公斤)。

输出

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

样例输入

6 3
20 30 50 80 100 120

样例输出

180

提示

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

数据范围：

30% 1<=n<=10；5<=m<=10;

60% 1<=n<=100；5<=m<=20;

100% 1<=n<=10000; 100<=m<=1000；1<=体重<=10000;