很好的搜索：

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



Input



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



Output



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



Sample Input





5 3

1 3 5 7 9

5 3

89 59 68 35 29



Sample Output





8

89