#include<bits/stdc++.h> using namespace std; #define fastio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define int long long #define pb push_back #define show(x) cout<<#x<<" : "<<x<<endl; #define gcd __gcd #define ff first #define ss second #define mp make_pair #define inf INT_MAX #define lb lower_bound #define ub upper_bound #define vec vector<int> #define mapint map<int,int> #define mapchar map<char,int> #define maplist map<int,vec> #define sum accumulate #define setitr set<int>::iterator #define mapitr map<int,int>::iterator #define pii pair<int,int> #define maxheap priority_queue<int> #define minheap priority_queue<int,vector<int>,greater<int> > const int zero =0; const int pri1 =998244353; int limit=pow(10,14); int msb(int n) { if (n == 0) return 0; int ms = 0; n = n / 2; while (n != 0) { n = n / 2; ms++; } return (1 << ms); } int maxa(int x,int y) { if(x>y) return x; else return y; } int mini(int x,int y) { if(x<y) return x; else return y; } int mini(int x,int y,int z) { if(x<=y and x<=y) return x; if(y<=z and y<=x) return y; if(z<=x and z<=x) return z; } int maxa(int x,int y,int z) { if(x>=y and x>=z) return x; if(y>=x and y>=z) return y; if(z>=x and z>=y) return z; } bool find(vector<int>&v,int val) { auto it=find(v.begin(),v.end(),val); if(it!=v.end()) return true; else return false; } bool find(set<int>&v,int val) { auto it=find(v.begin(),v.end(),val); if(it!=v.end()) return true; else return false; } int freq(vector<int>&v,int val) {return count(v.begin(),v.end(),val);} int power(int x,int y,int p ) { int res=1; x%=p; while(y>0) { if(y&1) res=(res*x)%p; y=y>>1; x=(x*x)%p; } return res; } int modi(int x) { return power(x,pri1-2,pri1); } int lcm(int x,int y) { return ((x*y)/(gcd(x,y))); } int find_sorted(vector<int>&v,int value) { auto it=lb(v.begin(),v.end(),value); if(it-v.begin()==v.size()) { return -1; } else return it-v.begin(); } int ncr(int n,int r,vector<int>&fact) { return (((fact[n]*modi(fact[r]))%pri1)*((modi(fact[n-r]))%pri1)%pri1); } int first_pos(vector<int>&v,int val) { for(int i=0;i<v.size();i++) if(v[i]==val) return i; return -1; } void input(vector<int> &a,int n){ a.resize(n); for(int i=0;i<n;i++) cin>>a[i]; } void output(vector<int> &v) { for(auto it:v) cout<<it<<" " ;} void factor(int n,vector<int>&v) { for(int i=1;i*i<=n;i++) { if(n%i==0 and n/i==i) v.pb(i); else if(n%i==0 and n/i!=i) { v.pb(i); v.pb(n/i); } }} void sieve(int n,vector<int>&prime) { int p=2; while(p*p<=n){ if(prime[p]) { for(int i=p*p;i<n+1;i+=p) prime[i]=0; } p+=1; } } void prefix(vector<int>&v,vector<int>&prefix){ for(int i=0;i<v.size();i++) { if(i==0) prefix.pb(v[0]); else {prefix.pb(prefix.back()+v[i]);} } } void str_vec(string &s,vector<int>&v) { for(int i=0;i<s.size();i++) v.pb(s[i]-'0'); } void vec_str(string &s,vector<int>&v) { for(int i=0;i<v.size();i++) s+=to_string(v[i]); } void eraser(vector<int>&v,int val) { for(int i=0;i<v.size();i++) { if(v[i]==val) { v.erase(v.begin()+i); return; } } } int unique(vector<int>&v) { set<int>s; for(int i=0;i<v.size();i++) s.insert(v[i]); return s.size(); } // ################################################################################################################################## /* tree functions - input, subtree size solver , parent finder , distance solver */ void tree_input(int n,map<int,vector<int>>&m) { int e=n-1; int x,y; while(e) { cin>>x>>y; m[x].pb(y); m[y].pb(x);e-=1; } } void subtre(mapint &subtree,vec &visited,int node,maplist &m) { visited[node]=1; subtree[node]+=1; for(auto it:m[node]) { if(visited[it]==0) { subtre(subtree,visited,it,m); subtree[node]+=subtree[it]; } } } void parent(mapint &pr,int node,vec &visited,maplist &m) { visited[node]=1; for(auto it:m[node]) { if(visited[it]==0) { pr[it]=node; parent(pr,it,visited,m); } } } void distance(vec &visited,int node,maplist &m,vec &dis) { visited[node]=1; for(auto it:m[node]) { if(visited[it]==0) { visited[it]=1; dis[it]=dis[node]+1; distance(visited,it,m,dis); } } } //########################################################################################################################## void solve() { int n,k,x; cin>>n>>k>>x; int dp[n+1][k+1][2]; memset(dp,0,sizeof(dp)); vec z; input(z,n); int maxa=0; for(int i=0;i<n;i++) { for(int j=0;j<k+1;j++) { if(i+1<j) { dp[i][j][0]=-INT_MAX; dp[i][j][1]=-INT_MAX; continue; } if(i==0 and j==0) { dp[i][j][0]=max(zero,z[i]-x); dp[i][j][1]=dp[i][j][0]; } else if(i==0 and j==1) { dp[i][j][0]=max(z[i]+x,zero); dp[i][j][1]=dp[i][j][0]; } else if(j==0) { dp[i][j][0]=max(dp[i-1][j][0]+z[i]-x,zero); dp[i][j][1]=max(dp[i-1][j][1],dp[i][j][0]); } else { dp[i][j][0]=max({dp[i-1][j-1][0]+z[i]+x,dp[i-1][j][0]+z[i]-x,zero}); dp[i][j][1]=max({dp[i][j][0],dp[i-1][j][1],dp[i-1][j-1][1]}); } if(j==k) { maxa=max(maxa,dp[i][j][1]); } } } cout<<maxa<<endl; } //############################################################################################################################ signed main() { int tt=1; fastio(); cin>>tt; while(tt--){ solve(); } return 0; }