玄关。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=5e5+5;
int n,k,a[N],q[N],head,tail;
ll sum[N],dp[N];
double slope(int x,int y) {
	return 1.0*(dp[y]-sum[y]+1ll*y*a[y+1]-dp[x]+sum[x]-1ll*x*a[x+1])/(a[y+1]-a[x+1]);
}
void solve() {
	cin>>n>>k;k--;
	for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
	head=1,tail=0;
	dp[0]=q[++tail]=0;
	for(int i=1;i<=n;i++) {
		if(i<=k) {
			dp[i]=1e18;
			continue;
		}
		while(head<tail&&slope(q[head],q[head+1])<=i) head++;
		dp[i]=dp[q[head]]+sum[i]-sum[q[head]]-1ll*(i-q[head])*a[q[head]+1];
		while(head<tail&&slope(q[tail-1],q[tail])>=slope(q[tail],i-k)) tail--;
		q[++tail]=i-k;
	}
	cout<<dp[n]<<"\n";
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t;cin>>t;
	while(t--) solve();
	return 0;
}