https://codeforces.com/contest/1862/problem/E

容易发现就是维护一个长度至多为m的序列和 减去 i*d（i为最后选择看电影的是哪一天）

一开始没有把第0天的p是0用上，没想出来

维护非负序列和这里可以用一个set，有点类似于滑动窗口，当窗口出去的时候我们去掉最没用的那一项就可以了

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N = 2e5+10;

void solve()
{
	ll n,m,d;cin>>n>>m>>d;
	vector<int>a(n+10);
	for(int i=0;i<n;i++)cin>>a[i];
	
	set<pair<int,int>>st;
	ll ans = 0,sum = 0;
	
	for(int i=0;i<n;i++){
		ll cur = sum+a[i]-(i+1)*d;
		ans = max(ans,cur);
		
		if(a[i]>0){
			st.insert({a[i],i});
			sum+=a[i];
			if(st.size()>=m){
				sum-=(st.begin()->first);
				st.erase(st.begin());
			}
		} 
	}
	
	cout<<ans<<"\n";
	
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;cin>>_;
	while(_--)solve();
	return 0;
}