광인 수용소의 간수 배치

가장 위험한 범죄자만 모아 둔 수용소의 간수 배치를 맡았다. 감방 $L$개가 한 줄로 늘어서 있고 1번부터 $L$번까지 번호가 붙어 있다. $i$번 감방에는 광기 수치가 $C_i$인 수감자가 정확히 한 명 있다.

수감자 한 명마다 간수 한 명이 붙는 것이 가장 좋지만, 예산이 모자라 쓸 수 있는 간수는 $G$명뿐이다. 탈옥 위험의 총합이 가장 작아지도록 각 간수가 감시할 수감자를 정해야 한다.

간수 한 명은 서로 이웃한 감방만 맡는다. 아무 감방도 맡지 않는 간수가 있어도 된다. $i$번 감방 수감자의 탈옥 위험 $R_i$는 광기 수치 $C_i$와 그 수감자를 맡은 간수가 감시하는 수감자 수의 곱이다. $i = 1$부터 $i = L$까지 $R_i$를 모두 더한 값이 전체 탈옥 위험 $R$이다.

수감자 $L$명과 간수 $G$명이 주어질 때 $R$의 최솟값을 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에 수감자 수 $L$과 간수 수 $G$가 공백으로 구분되어 주어진다. 이어지는 $L$개 줄 가운데 $i$번째 줄에는 $i$번 감방 수감자의 광기 수치 $C_i$가 주어진다.

제한

• $1 \leq T \leq 22$
• $1 \leq L \leq 8000$
• $1 \leq G \leq 800$
• $1 \leq C_i \leq 10^9$

각 테스트 케이스마다 전체 탈옥 위험 $R$의 최솟값을 한 줄에 출력한다.