模拟赛场切了，但仔细算一下感觉题解区有些人的复杂度是错的，故来写一发题解。

思路其实很简单，显然不能直接暴力枚举横着和竖着放哪些。

考虑枚举横着放哪些，竖着的二分加贪心去放，但是直接算是 $10^9$ 级别的，感觉难以通过。

可以预处理出两个竖着的线之间的最大值，降低二分时 check 的复杂度，计算发现是 $10^8$ 次方级别，而且数据较水，轻松通过，最慢的点为 $83ms$，应该是你谷最快。

#include<bits/stdc++.h>
#define ll long long
#define R register
#define F(i,a,b) for(int i = (a);i<=(b);i++)
using namespace std;
inline int read(){R int x=0,t=1;R char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*t;}
const int N=22+10;
int n,m,r,s,a[N][N],p[N];
ll sm[N][N],sum,b[N][N],mx[N][N];
inline bool check(ll x)
{
	int last=1,r1=1;
	for(int i = 1;i<=s;i++){
		if(last>m) return 1;
		if(mx[last][last]>x) return 0;
		while(r1<=m && mx[last][r1]<=x){
			r1++;
		}
		r1--;
		if(mx[last][r1]<=x){
			r1++;
			last=r1;
		}
	}
	if(last>m) return 1;
	if(mx[last][m]<=x){
		return 1;
	}
	return 0;
}
inline void work()
{
	p[r+1]=n;
	for(int i = 1;i<=m;i++){
		for(int j = 1;j<=r+1;j++){
			b[j][i]=0;
			for(int k = p[j-1]+1;k<=p[j];k++){
				b[j][i]+=a[k][i];
			}
		}
	}
	for(int i = 1;i<=r+1;i++){
		for(int j = 1;j<=m;j++){
			sm[i][j]=sm[i][j-1]+b[i][j];
		}
	}
	for(int i = 1;i<=m;i++){
		for(int j = i;j<=m;j++){
			ll maxn=0;
			for(int k = 1;k<=r+1;k++){
				maxn=max(maxn,sm[k][j]-sm[k][i-1]);
			}
			mx[i][j]=maxn;
		}
	}
	if(!check(sum)) return;
	ll l=0,r=sum,ans=1e18;
	while(l<=r){
		int mid=l+r>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	sum=min(sum,ans);
	return;
}
void dfs(int x)
{
	if(x>r){
		work();
		return;
	}
	for(int i = p[x-1]+1;i<=n;i++){
		p[x]=i;
		dfs(x+1);
		p[x]=0;
	}
	return;
}
signed main()
{
	n=read(),m=read(),r=read(),s=read();
	F(i,1,n){
		F(j,1,m){
			a[i][j]=read();
			sum+=a[i][j];
		}
	}
	dfs(1);
	cout << sum << '\n';
	return 0;
}
/*

*/