#1573 숫자 구슬

49  1 s   128 MB  

Description


N개의 숫자 구슬이 <그림 1> 과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼 수 없고 따라서 그 순서를 바꿀수 없다.


<그림 1>


이 숫자 구슬을 M개 그룹으로 나누었을 때 각각의 그룹의 합 중 최대값이 최소가 되도록 하려 한다. 예를 들어 세 그룹으로 나눈다고 할 때 <그림 2>와 같이 그룹으로 나누면 그룹의 합은 각각 11, 15 , 18이 되어 그 중 최대값은 18이 되고 ,< 그림 3>과 같이 그룹을 나누면 각 그룹의 합은 각각 17, 12 , 15가 되어 그 중 최대값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최대값이 17보다 작게 만들수 없다.


<그림 2>

<그림 3>

각 그룹의 합 중 최대값이 최소가 되도록 M개의 그룹으로 나누는 방법을 계산하는 프로그램을 작성하시오.

Input


입력은 여러 개의 테스트 케이스로 이루어져 있다. 입력은 EOF로 종료된다.

각 테스트 케이스의 첫째 줄에 구슬의 개수 N과 그룹의 수 M 이 주어진다. 둘째 줄에는 각 구슬에 적힌 숫자가 왼쪽부터 차례로 주어진다. N은 300이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100이하의 자연수이다.

Output


각 테스트 케이스마다, 각 그룹의 합 중 최대 값이 최소가 되도록 M개의 그룹으로 나누었을때 그 최대값을 하나의 줄에 출력한다.

Sample Input

Sample Output

8 3
5 4 2 6 9 3 8 7
3 3
3 3 3
17
3

Source

KOI Regional 2004