Description

给你很多长度不定的木棒，将他们分成几组，每组中的总长度作为这组的标示值，请给出一种分组方法，能使得所有标示值中的最小值最大。

Input

多组，每组两行，第一行是一个N和K，代表有N根木棒，分成K组，第二行是N个数字，代表木棒的长度。（N不超过100，K不超过20，每根木棒长度不超过1000）

Output

输出所有标示值中的最小值的最大值。

Sample Input

5 3
1 3 5 7 9

Sample Output

8

HINT

Source