구간 나누기 2

$N$개의 수로 이루어진 1차원 배열이 있다. 이 배열을 $M$개 이하의 구간으로 나누어 구간 점수의 최댓값을 최소로 만들려고 한다. 구간은 다음 두 조건을 지켜야 한다.

1. 한 구간은 연속한 수 하나 이상으로 이루어진다.
2. 배열의 각 수는 정확히 한 구간에 속한다.

구간의 점수는 그 구간에 속한 수의 최댓값과 최솟값의 차이다.

예를 들어 배열이 $[1, 5, 4, 6, 2, 1, 3, 7]$이고 $M = 3$이라고 하자. $[1, 5]$, $[4, 6, 2]$, $[1, 3, 7]$로 나누면 세 구간의 점수는 4, 4, 6이고 그 최댓값은 6이다. $[1, 5, 4]$, $[6, 2, 1]$, $[3, 7]$로 나누면 세 구간의 점수는 4, 5, 4가 되고 최댓값은 5다. 두 방법 중 최댓값이 더 작은 쪽은 5이며, 최댓값을 5보다 작게 만드는 방법은 없다.

배열과 $M$이 주어질 때 구간 점수의 최댓값이 가질 수 있는 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 배열의 크기 $N$과 구간 개수의 상한 $M$이 주어진다. ($1 \le N \le 5000$, $1 \le M \le N$)

둘째 줄에 배열에 들어 있는 수가 순서대로 주어진다. 각 수는 1 이상 10,000 이하의 자연수다.

첫째 줄에 구간 점수의 최댓값의 최솟값을 출력한다.