리스트 자르기

정수 $N$개로 이루어진 리스트 $L$이 주어진다.

리스트 $L = \{l_1, l_2, \ldots, l_N\}$을 인덱스 $i$에서 자르면 비어 있지 않은 두 조각 $\{l_1, \ldots, l_i\}$과 $\{l_{i+1}, \ldots, l_N\}$으로 나뉜다. 이렇게 잘라 나온 조각을 다시 자르는 식으로 모두 $K - 1$번 자르면 조각이 $K$개 남고, 각 조각은 $L$에서 연속한 원소로 이루어진다.

$i$번째 조각의 최댓값을 $M_i$, 최솟값을 $m_i$라 하고 $d_i = M_i - m_i$로 정의한다.

$ans = \sum_{i=1}^{K} d_i$가 최소가 되도록 $L$을 조각 $K$개로 자르고, 그때의 $ans$를 구하시오.

첫째 줄에 테스트 케이스의 개수 $TC$가 주어진다 ($1 \le TC \le 120$).

각 테스트 케이스 앞에는 빈 줄이 하나 있다. 테스트 케이스의 첫째 줄에는 두 정수 $N$과 $K$가 주어진다 ($1 \le K \le N \le 400$). 둘째 줄에는 리스트 $L$의 원소 $N$개가 주어지며, 모두 $1000$보다 작은 양의 정수다. $L$의 원소가 서로 다르다는 보장은 없다.

각 테스트 케이스마다 $ans$를 한 줄에 출력한다.

$L = 8\ 1\ 5\ 4\ 7$인 경우를 보자.

$K = 2$면 $\{8\}$과 $\{1, 5, 4, 7\}$로 잘라 $(8 - 8) + (7 - 1) = 6$이 된다. $K = 3$이면 $\{8\}$, $\{1\}$, $\{5, 4, 7\}$로 잘라 $0 + 0 + 3 = 3$이다. $K = 4$면 $\{8\}$, $\{1\}$, $\{5, 4\}$, $\{7\}$로 잘라 $0 + 0 + 1 + 0 = 1$이다.

$K = 1$이면 답은 리스트 전체의 최댓값에서 최솟값을 뺀 값이고, $K = N$이면 조각마다 원소가 하나뿐이라 답은 $0$이다.