비슷한 간격

마침내 식당 체인을 소유하는 꿈이 이루어졌습니다. 마케팅 회사와 상담했고, 도시에서 식당을 가장 잘 배치하는 방법에 대한 지침을 받았습니다.

이 회사는 한 도로를 따라 식당 후보지를 찾아냈습니다. 각 후보지에는 식당을 한 곳만 세울 수 있습니다. 인플루언서 미디어 효과를 극대화하려면 이 도로를 따라 식당 몇 곳을 짓고 모두 같은 시점에 엽니다. 고객을 체인으로 끌어들이는 가장 좋은 방법은 도로를 따라 모든 식당을 비슷한 간격으로 짓는 것입니다. 이렇게 배치하면 보행자 회상 일관성이 극대화되는데, 요즘 마케팅에서 유행하는 개념입니다.

구체적으로, $a$를 인접한 두 식당 사이 거리의 최댓값, $b$를 인접한 두 식당 사이 거리의 최솟값이라고 합니다. $a-b$가 최소가 되도록 식당을 배치하세요.

첫째 줄에 두 정수 $N$과 $K$가 주어집니다($2 \le N \le 100$, $2 \le K \le N$). $N$은 식당 후보지의 개수이고, $K$는 지을 식당의 개수입니다. 둘째 줄에는 $N-1$개의 정수 $d_1,\dots,d_{N-1}$이 주어집니다($0 \le d_i < 2^{31}$). $d_i$는 후보지 $i$와 $i+1$ 사이의 거리입니다.

$a-b$의 값을 출력하세요.

두 번째 예시에서 최적 배치는 후보지 $1$, $3$, $5$, $6$에 식당을 짓는 것입니다. 이때 인접한 식당 사이 거리는 차례대로 $d_1+d_2$, $d_3+d_4$, $d_5$입니다. 따라서 $a=10$(이 값들의 최댓값), $b=8$(최솟값)이고 $a-b=2$입니다.

세 번째 예시에서 최적 배치는 후보지 $3$, $4$, $6$, $7$, $8$에 식당을 짓는 것입니다. 이때 거리는 차례대로 $d_3$, $d_4+d_5$, $d_6$, $d_7$입니다. 따라서 $a=32$, $b=18$이고 $a-b=14$입니다.