봉화대 설치

문제 정보

문제

봉화는 나라에 재난이 일어났음을 알리기 위해 봉화대에서 올리는 횃불을 말한다. 낮에는 연기를 피워 올리고 밤에는 횃불로써 급박한 상황을 전달했던 비상연락시설이다.

RUN 왕국에서는 오랑캐들의 침략에 대비해 봉화대를 설치하기로 했다. 오랑캐가 국경에 침입해오면, 국경 가장 가까이에 있는 봉화대에서 불을 올린다. 봉화대에 불이 오르면 그 봉화가 보이는 다음 봉화대에서 또 불을 올린다. 이런 방식으로 국경에서 수도까지 봉화를 통해 연락을 취할 것이다.

봉화대를 설치하기 위해 우선 국경과 수도 사이에 같은 간격으로 N개의 후보 지점을 선정했다. 모든 후보 지점에서는 앞뒤로 각각 P개의 후보 지점이 보인다. 국경과 수도에서도 역시 P개의 후보 지점이 보인다. 다시 말해 국경에 가장 가까운 P개의 후보 지점 중에 적어도 한 곳에는 봉화대를 설치해야 하고, 수도에 가장 가까운 P개의 후보 지점 중에 적어도 한 곳에도 봉화대를 설치해야 한다.

각 후보 지점을 봉화대로 만들기 위해서는 공사가 필요한데, 공사 비용은 지점의 지형에 따라 다르다. 국경에서 수도까지 최소의 공사 비용으로 봉화를 설치하면 얼마의 비용이 들까?

입력

첫째 줄에는 테스트 케이스의 개수 T가 주어진다.
각 테스트 케이스의 첫 줄에는 후보 지점의 개수 N과 봉화대의 시야 P가 주어진다. (2 ≤ N ≤ 100000, 1 ≤ P < N)
다음 줄에는 N개의 각 후보 지점에 봉화대를 설치할 때에 드는 공사 비용이 주어진다.
공사 비용은 1000 이하의 자연수다.

출력

각 테스트 케이스에 대해 최소의 공사 비용을 한 줄에 하나씩 출력한다.

예제 입력

1
8 3
3 1 4 2 3 4 2 1

예제 출력

5

노트

2개의 댓글이 있습니다.