#include <bits/stdc++.h>
using namespace std;
const int MAX_N=20001;
const int MAX_M=101;
const int MAX_K=101;
const int INF=1000000007;
int n,m,k;
vector<vector<int>> a;
vector<int> ind;
vector<int> prevs;
vector<int> score;
vector<vector<vector<int>>> hide;
int dp1[2][MAX_K*MAX_M+1][MAX_M+1]={0};
int dp2[2][MAX_K*MAX_M+1]={0};
bool nstrict[MAX_N]={0};
bool compare(int i, int j)
{
if(score[i]==score[j])
{
return i>j;
}
return score[i]<score[j];
}
int leq(const vector<int>& x, int y)
{
if(x.empty() || y<x[0])
{
return -1;
}
if(x.back()<=y)
{
return x.back();
}
int lo=0;
int hi=x.size();
while(lo<hi-1)
{
int mid=(hi+lo)/2;
if(x[mid]<=y)
{
lo=mid;
}
else
{
hi=mid;
}
}
return x[lo];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>k;
a.assign(n,vector<int>(m));
score.assign(n,0);
ind.resize(n);
prevs.assign(n,0);
for(int c1=0; c1<n; c1++)
{
for(int c2=0; c2<m; c2++)
{
cin>>a[c1][c2];
score[c1]+=a[c1][c2];
}
ind[c1]=c1;
}
sort(ind.begin(),ind.end(),compare);
for(int c1=0; c1<n; c1++)
{
int i=ind[c1];
if(c1>0)
{
prevs[i]=score[ind[c1-1]];
if(i>ind[c1-1])
{
nstrict[i]=true;
}
}
}
hide.resize(n);
for(int c1=0; c1<n; c1++)
{
int xhid=score[c1]-prevs[c1];
for(int sc=0; sc<=xhid; sc++)
{
for(int c=0; c<=m; c++)
{
dp1[1][sc][c]=0;
}
}
dp1[1][0][0]=1;
for(int problem=0; problem<m; problem++)
{
int me=problem%2;
int nme=(problem+1)%2;
for(int sc=0; sc<=xhid; sc++)
{
for(int c=0; c<=m; c++)
{
dp1[me][sc][c]=0;
if(dp1[nme][sc][c]==1)
{
dp1[me][sc][c]=1;
}
if(c>0 && sc>=a[c1][problem] && dp1[nme][sc-a[c1][problem]][c-1]==1)
{
dp1[me][sc][c]=1;
}
}
}
}
int me=(m+1)%2;
vector<vector<int>> hides(m+1);
for(int c=0; c<=m; c++)
{
for(int sc=0; sc<=xhid; sc++)
{
if(dp1[me][sc][c]==1)
{
hides[c].push_back(sc);
}
}
}
hide[c1]=hides;
}
for(int c1=n-1; c1>=0; c1--)
{
int i=ind[c1];
int me=c1%2;
int nme=(c1+1)%2;
int xhid=score[i]-prevs[i];
for(int before=0; before<=xhid; before++)
{
dp2[me][before]=INF;
for(int c=0; c<=m; c++)
{
int hides=leq(hide[i][c],before-int(nstrict[i]));
if(hides==-1)
{
continue;
}
int r=score[i]-hides+k*c;
int nex=0;
if(c1<n-1)
{
nex=score[ind[c1+1]]-r;
}
if(nex<0)
{
continue;
}
dp2[me][before]=min(dp2[me][before],m-c+dp2[nme][nex]);
}
}
}
cout<<dp2[0][score[ind[0]]]<<endl;
return 0;
}
