#pragma GCC optimize(2)
#include<iostream>
#include<cstring>

using namespace std;

const int N = 2e5 + 10;

int f[N][20 + 10],ff[N][20+10], a[N], s[N],lg[N],n, m, k,t,res;

void st()
{
    memset(ff, 0, sizeof ff);
    for (int j = 0; j <lg[n]+1; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            if (j == 0) ff[i][j] = i;
            else {
                if (s[ff[i][j - 1]] > s[ff[i + (1 << j - 1)][j - 1]]) {
                    ff[i][j] = ff[i][j - 1];
                }
                else {
                    ff[i][j] = ff[i + (1 << j - 1)][j - 1];
                }
            }
        }
    }
}
int main()
{
    scanf("%d", &t);
    for (int i = 2; i < N; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 1; i <= t; i++) {
        scanf("%d%d%d", &n, &k, &m);
        res = 0;
        memset(f, -0x3f3f3f3f, sizeof f);
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[j]);
            a[j] = a[j] - m;
            s[j] = s[j - 1] + a[j];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k&&j<=i; j++) {
                if (j <= i - 1) {
                    f[i][j] = max(f[i][j], f[i - 1][j]);
                }
                f[i][j] = max(f[i][j], s[i] - s[i - j]);
            }
        }
        for (int i = 1; i <= 20&&i<=n; i++) {
            if (m >= 0) {
                res = max(res, f[n][i] + 2 * m * min(i, k));
            }
            else {
                res = max(res, f[n][i] + 2 * m * (max(0, k - (n - i))));
            }
            
        }
        st();
        int tem=0,tems=0,left = 0, right = 0;
        for (int i = 0; i <= n; i++) {
            int l = i + 1, r = n - k + l - 1;
            if (m >= 0) r = n;
            if (l > r) continue;
            int len = r - l + 1;
            int le = ff[i][lg[len]];
            int ri = ff[r-(1 << lg[len])+1][lg[len]];
            if (s[ri] >= s[le]) tem = ri;
            else tem = le;
            if (s[tem] - s[i] > tems) {
                tems = s[tem] - s[i];
                left = i + 1;
                right = tem;
            }
        }
        if (m >= 0) {
            res = max(res, tems + 2 * m * min(k,(right - left + 1)));
        }
        else {
            res = max(res, tems + 2 * m * max(0, k - (n-(right - left + 1))));
        }
        
        printf("%d\n", res);
    }

    return 0;
}