Problem E: 搬书

上一题 正确率: $80.95\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $21$ 正确数量 $17$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 贪心

Description

学校的新图书馆建好了，于是要把老图书馆的书搬到新馆。老图书馆的书非常多，而且都分门别类排放好了。搬书就成了个大问题，不仅要把所有书都搬过去，而且不能把顺序弄乱了。

大家商量决定，先用箱子把书按顺序装好后再搬过去。每本书都有一定的体积，一个箱子只能装体积之和不大于它容积的书。箱子要从市场上买，大家都不想浪费。所以就有了一个问题，如果要用m个箱子把所有书装好，那么每个箱子容积至少要是多少呢？假设每个箱子的大小是一样的。

Input

输入第一行为两个整数n和m(1<=n<=10000,1<=m<=100)，表示一共有n本书，使用m个箱子。

接下来一行有n个整数表示每本书的体积v(1<=v<=10000)。

注：书要按顺序装进箱子，所以只有连续的几本书才能装进一个箱子。

Output

每组数据输出占一行，输出每个箱子容积至少是多少。

Sample Input复制

2 1
1 3

Sample Output复制

4