原题链接：https://atcoder.jp/contests/abc159/tasks/abc159_e

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=15,M=1010;
int h,w,k;
int s[N][M];

int main(){
    cin>>h>>w>>k;

    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++) {
            char m;
            cin>>m;
            int e=m-'0';
            s[i][j]=e+s[i-1][j]+s[i][j-1]-s[i-1][j-1];    
            //这题出题人良心，直接把要算的设置成1，不要算的设置成0
        }
    }

    int minsum=h+w-2;
    for(int i=0;i<(1<<(h-1));i++){//枚举横切情况
        vector<int> q;
        q.push_back(0);//记得加第0条边界线，方便统一处理
        int sum=0;

        for(int j=0;j<h-1;j++){
            if(i>>j&1) {
                q.push_back(j+1);
                sum++;
            }
        }
        q.push_back(h);//最外面的边界线，处理最后一个格子和不切的情况

        bool flag=true;
        int lastline=0;
        for(int j=1;j<=w;j++){//贪心纵切
            int wmax=0;
            for(int d=1;d<q.size();d++){
                wmax=max(wmax,s[q[d]][j]-s[q[d]][lastline]-s[q[d-1]][j]+s[q[d-1]][lastline]);
            }
            if(wmax>k){
                if(j==1){
                    flag=false;
                    break;
                }
                sum++;
                lastline=j-1;
            }
        }
        if(!flag) continue;
        minsum=min(minsum,sum);
    }
    cout<<minsum<<endl;
    return 0;
}