N개의 숫자 구슬이 <그림 1>과 같이 막대에 꿰어져 일자로 놓여 있다.

이들 구슬은 막대에서 빼낼수 없고 따라서 바꿀 수 없다.

이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최대값이 최소가 되도록 하려 한다.

예를 들어 세 그룹으로 나눈다고 할 때 <그림 2>와 같이 그룹을 나누면

그룹의 합은 각각 11, 15, 18이 되어 그 중 최대값은 18이 되고,

<그림 3>과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최대값은 17이 된다.

숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최대값이 17보다 작게 만들 수는 없다.

각 그룹의 합 중 최대값이 최소가 되도록 M개의 그룹으로 나누었을 때,

그 최대값을 출력하는 프로그램을 작성하시오.

숫자구슬(medium) timer 1s memory 256MB

숫자구슬(medium) 1s 256MB