#include <stdio.h>
#define MAX 100000 + 2

int TC;
int N;
int P;
int ARR[MAX+MAX];
unsigned long long sum;
int from1, to1;
int from2, to2;
int start, end;
int min, minindex;

int main(void)
{
   scanf("%d",&TC);

    for(int i=0;i<TC;i++)
    {
        scanf("%d %d", &N, &P);

        for(int j1=0;j1<N;j1++)
        {
            scanf("%d", &ARR[j1+1]);
        }

        // 예외1 : P=1 인 경우
        if(P==1) {
            for(int j2=1;j2<N+1;j2++)
                sum = sum + ARR[j2];

            printf("%llu\n",sum);
            sum=0;

            min = 0;
            minindex = 0;
            for(int j3=0;j3<N;j3++)
                ARR[j3+1]=0;
            continue;
        }
        // 예외2 : N <= P 인 경우 가장 작은 곳 1개가 답
        if(N<=P) {
            sum = MAX;
            for(int j4=1;j4<N+1;j4++)
            {
                if(sum>ARR[j4]) sum = ARR[j4];
            }
            printf("%llu\n",sum);
            sum=0;

            min = 0;
            minindex = 0;
            for(int j5=0;j5<N;j5++)
                ARR[j5+1]=0;
            continue;
        }

        // 처음부터 시작하여 P개씩 묶고, 마지막 부터 시작하여 P개씩 묶는다.
        // 겹치는 부분중에서 최소 값을 찾되 동일한 값이면 나중것을 선택한다.
        // 이렇게 선택된 것을 모두 더하면 답이 된다.
        for(;minindex<N+1;)
        {
            from1 = minindex + 1;
            to1 = from1+P-1;
            from2 = minindex + (N-minindex)%P + 1;
            to2 = from2+P-1;

            min = MAX;
            start = from2;
            end = to1;

            for(int k=start;k<=end;k++)
            {
                if(ARR[k]<=min)
                {
                    minindex = k;
                    min = ARR[k];
                }
            }

            // 검토, 겹치는 값보다 이전의 값이 작은 경우도 있으므로 그것을 체크한다.
            for(int l=minindex-1;l>=from1;l--)
            {
                if(l+P+1>N+1) break;
                for(int m=1;m<=P;m++)
                {
                    if(l+m < minindex) break;
                    if(ARR[l]+ARR[l+m] <= min)
                    {
                        minindex = l;
                        min = ARR[l];
                    }
                }
            }

            //printf("%d ",ARR[minindex]);
            sum = sum + min;

        }

        printf("%llu\n",sum);
        sum=0;

        min = 0;
        minindex = 0;
        for(int j6=0;j6<N;j6++)
            ARR[j6+1]=0;
    }

    return 0;
}