#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e5 + 10;
typedef long long LL;
LL a[N];
LL s[N];
LL f[N];
int T, n, k;
int q[N];

LL get_y(int j)
{
    return f[j] - s[j] + j*a[j+1];
}

LL get_x(int j)
{
    return a[j + 1];
}


int main()
{
    cin >> T;
    while(T--)
    {
        cin >> n >> k;
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i];
            s[i] = s[i - 1] + a[i];
        }
        memset(f, 0x3f, sizeof f);
        f[0] = 0;
        int hh = 0, tt = 0;
        q[0] = 0;
        for(int i = 1; i <= n; i++)
        {
            while(hh < tt && (get_y(q[hh + 1]) - get_y(q[hh])) <= i * (get_x(q[hh + 1]) - get_x(q[hh]))) hh++;
            int j = q[hh];
            f[i] = f[j] - s[j] + j*a[j+1] - i*a[j+1] + s[i];
            if(i - k + 1 >= k)
            {
                while(hh < tt && (get_y(q[tt]) - get_y(q[tt - 1])) * (get_x(i-k+1) - get_x(q[tt])) >= (get_y(i-k+1) - get_y(q[tt])) * (get_x(q[tt]) - get_x(q[tt-1]))) tt--;
                q[++ tt] = i - k + 1;
            }


        }
        cout << f[n] << endl;
    }
    return 0;
}