首先我们发现将一段数变为同一个数比间隔着搞肯定优，
因为数列是升序的，
然后不难得到方程式f[i]=min(f[j]+sum[i]-sum[j]-(i-j)*a[j+1]) (i-j>=m)
简单的斜率优化不多说
注意这道题最优解有选择范围，也就是说要延迟入队
var a,s,f:array[..] of int64;
q:array[..] of longint;
j,t,i,n,m,h,r:longint; function G(j,k:int64):int64;
begin
exit(f[j]-f[k]+s[k]-s[j]+a[j+]*j-a[k+]*k);
end; function P(j,k:int64):int64;
begin
exit(a[j+]-a[k+]);
end; function value(i,j:int64):int64;
begin
exit(f[j]+s[i]-s[j]-a[j+]*(i-j));
end; begin
readln(t);
while t> do
begin
dec(t);
readln(n,m);
s[]:=;
for i:= to n do
begin
read(a[i]);
s[i]:=s[i-]+a[i];
end;
f[]:=;
q[]:=;
h:=;
r:=;
for i:= to n do
begin
while (h<r) and (G(q[h+],q[h])<=int64(i)*P(q[h+],q[h])) do inc(h);
f[i]:=value(i,q[h]);
if (i>=*m-) and (i<>n) then
begin
while (h<r) and (G(i-m+,q[r])*P(q[r],q[r-])<=G(q[r],q[r-])*P(i-m+,q[r])) do dec(r);
inc(r);
q[r]:=i-m+;
end;
end;
writeln(f[n]);
end;
end.