감시 구역 나누기

Albert는 지하 연구소의 보안을 강화하려고 감시용 로봇을 사용해 보려 한다. 지하 연구소에는 방이 $N$개 있으며, 왼쪽부터 오른쪽까지 1번부터 $N$번까지 번호가 붙어 있다. 아래 그림처럼 긴 복도 형태이며, 이 경우 $N = 5$이다.

$i$번째 방과 $i+1$번째 방 사이의 거리는 $d_i$이다. 아래 그림의 경우 $d = [2, 3, 1, 4]$이다. 편의상 두 방 $i, j$ 사이의 거리를 $D(i, j)$로 나타낸다. 따라서 $i \lt j$일 때 $D(i, j) = \sum_{i \le k \lt j} d_k$이고, $D(i, i) = 0$이다.

그림의 경우 $D(1, 4) = d_1+d_2+d_3 = 6$이고, $D(3, 4) = d_3 = 1$이다.

Albert는 감시용 로봇 $M$대를 쓰고 싶다. 먼저 $N$개의 방을 $M$개의 연속한 구역으로 나누고, 각 구역을 로봇 한 대가 24시간 감시하게 한다. 각 구역은 하나 이상의 연속한 방으로 이루어지며, 각 방은 반드시 하나의 구역에 속해야 한다. 로봇은 자신이 맡은 구역의 방들을 감시하는데, 이때 필요한 에너지는 그 구역에 속한 서로 다른 방 사이 거리의 총합이다. 구역이 $i$번 방부터 $j$번 방까지 포함할 때, 이 구역을 감시하는 데 필요한 에너지 $S(i, j)$는 $S(i, j) = \sum_{i \le k \le l \le j} D(k, l)$이다. 이 정의에 따르면 $S(i, i) = 0$이다. 이 경우 로봇은 $i$번 방에 가만히 있으면 되므로 에너지를 거의 쓰지 않는다.

$M = 2$인 경우 5개의 방을 2개의 구역으로 나누는 방법은 4가지이다. 곡선은 두 방 사이의 거리 $D(\cdot, \cdot)$ 값을 나타낸다.

• 첫 번째 방법은 [1, 3]과 [4, 5]로 나누는 경우이다. 첫 번째 구역의 에너지는 $D(1, 2) + D(1, 3) + D(2, 3) = 10$이고, 두 번째 구역의 에너지는 $D(4, 5) = 4$이다.
• 두 번째 방법은 [1, 2]와 [3, 5]로 나누는 경우이다. 각 구역의 에너지는 2와 10이다.
• 세 번째 방법은 [1, 1]과 [2, 5]로 나누는 경우이다. 첫 번째 구역의 에너지는 0이고, 두 번째 구역의 에너지는 25이다.
• 네 번째 방법은 [1, 4]와 [5, 5]로 나누는 경우이다. 첫 번째 구역의 에너지는 21이고, 두 번째 구역의 에너지는 0이다.

배터리 용량이 너무 크면 비용이 많이 들기 때문에, Albert는 각 로봇이 필요로 하는 에너지의 최댓값을 최소로 만들고 싶다. 즉, $M$개 구역이 필요로 하는 에너지의 최댓값을 최소화한다. 위 경우에는 첫 번째 또는 두 번째 방법이 최적이며, 정답은 10이다.

Albert를 도와 $N$, $M$, $d$가 주어졌을 때, $N$개의 방을 $M$개의 연속한 구역으로 나눌 때 각 구역이 필요로 하는 에너지 최댓값의 최솟값을 구하자.

첫 번째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 $N$과 $M$이 공백으로 구분되어 주어진다. 둘째 줄에는 $N-1$개의 정수가 공백으로 구분되어 주어지며, 이는 $d_1, d_2, \dots, d_{N-1}$의 값이다.

각 테스트 케이스의 정답을 한 줄에 하나씩 출력한다.

• $1 \le T \le 20$
• $4 \le N \le 30000$
• $1 \le M \le N$
• $1 \le i \lt N$인 모든 $i$에 대하여: $1 \le d_i \le 10^6$