#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,m,a[N],t,k,d,dp[N],kk[N];
deque<int> dq;
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld%lld%lld",&n,&m,&k,&d);
		for(int i=1;i<=n;i++) kk[i]=0;
		m-=2;
		d++;
		int sb,sp=0;
		for(int i=1;i<=n;i++){
			int ans=0x7fffffffffffffff;
			while(!dq.empty()){
				dq.pop_back();
			}
			cin>>sb;
			for(int j=1;j<=m;j++){
				scanf("%lld",&a[j]);
				a[j]++;
				dp[j]=a[j];
			}cin>>sb;
			for(int j=1;j<=m;j++){
				while(!dq.empty()&&dq.front()<j-d){
					dq.pop_front();
				}if(j>d){
					dp[j]+=dp[dq.front()];
				}
				while(!dq.empty()&&dp[dq.back()]>dp[j]){
					dq.pop_back();
				}dq.push_back(j);
			}for(int j=m-d+1;j<=m;j++){
				ans=min(ans,dp[j]);
			}kk[i]=ans;
		}sort(kk+1,kk+n+1);
		for(int i=1;i<=k;i++) sp+=kk[i]+2;
		printf("%lld\n",sp);
	}
	return 0;
}