#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 2e5 + ;

int h[N], n, k, m;

LL pre[N], sum[N];

LL cost[][N];

LL Get(int l, int r){

    return pre[r] - pre[l] - (r-l) * sum[l];

}

priority_queue<LL, vector<LL>, greater<LL> > pq;

void solve(LL pre[], LL now[], int L, int R, int l, int r){

    if(l > r) return ;

    int mid = l+r >> ;

    now[mid] = _INF;

    int p = L;

    for(int i = min(mid, R); i >= L; --i){

        if(pre[i] - Get(i, mid) > now[mid]){

            now[mid] = pre[i] - Get(i, mid);

            p = i;

        }

    }

    solve(pre, now, L, p, l, mid - );

    solve(pre, now, p, R, mid + , r);

}

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        scanf("%d%d%d", &n, &k, &m);

        for(int i = ; i <= n; ++i){

            scanf("%d", &h[i]);

            sum[i] = sum[i-] + h[i];

            pre[i] = pre[i-] + sum[i];

            cost[][i] = -pre[i];

            pq.push(1ll * (n - i + ) * h[i]);

            if(pq.size() > m) pq.pop();

        }

        int now = , pre = ;

        for(int i = ; i <= k; ++i){

            swap(now, pre);

            solve(cost[pre], cost[now], , n, , n);

        }

        LL ans = cost[now][n];

        while(!pq.empty()) {ans += pq.top(); pq.pop();}

        printf("%lld\n", ans);

    }

    return ;

}