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

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

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

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

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

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

2 1
1 3

4