#include
     
      #define fi first#define se second#define INF 0x3f3f3f3f#define LNF 0x3f3f3f3f3f3f3f3f#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)#define pqueue priority_queue#define NEW(a,b) memset(a,b,sizeof(a))const double pi=4.0*atan(1.0);const double e=exp(1.0);const int maxn=1e4+8;typedef long long LL;typedef unsigned long long ULL;const LL mod=1e9+7;const ULL base=1e7+7;const int maxp=26+5;using namespace std;LL a[maxn],f[maxn];LL g[maxn],gg[maxn];LL dp[maxn][58];LL q[58][maxn];LL l[58],r[58];LL gdp(int i,int j,int k) {
   return dp[j][k]-gg[j]-g[j]*(i-j)+gg[i];}LL gfz(int j,int h,int k) {
   return dp[j][k]-gg[j]+g[j]*(j)-(dp[h][k]-gg[h]+g[h]*(h));}LL gfm(int j,int h) {
   return g[j]-g[h];}int main(){    int t;    scanf("%d",&t);    int n,m,k;    while(t--){        scanf("%d%d%d",&n,&k,&m);        for(int i=1;i<=n;i++){            scanf("%lld",&a[i]);            g[i]=g[i-1]+a[i];            gg[i]=g[i]+gg[i-1];        }        for(int i=1;i<=k;i++){            l[i]=r[i]=1;            q[i][l[i]]=0;        }        for(int i=1;i<=n;i++){            for(int j=1;j<=i&&j<=k+1;j++){                while(l[j-1]
      
       <=i*gfm(q[j-1][l[j-1]+1],q[j-1][l[j-1]])) l[j-1]++;                dp[i][j]=gdp(i,q[j-1][l[j-1]],j-1);                while(l[j]
       
        <=gfm(i,q[j][r[j]])*gfz(q[j][r[j]],q[j][r[j]-1],j)) r[j]--;                q[j][++r[j]]=i;            }        }        for(int i=1;i<=n;i++){            f[i]=a[i]*(n-i+1);        }        sort(f+1,f+1+n);        LL ans=0;        for(int i=n;i>=n-m+1;i--){            ans+=f[i];        }        ans-=dp[n][k+1];        printf("%lld\n",ans);    }}