#include <bitset>
#include <iostream>
// #include <cassert>
#include <vector>
#include <algorithm>
#include <climits>

#include <stack>
#include <queue>
// #include <deque>
#include <set>
#include <map>
// #include <string>
// #include <unordered_set>
// #include <unordered_map>

#include <tuple>
// #include <cmath>
// #include <numeric>

using namespace std;
typedef long long ll;
typedef pair<long,long> pll;
typedef pair<int,int> pii;
typedef pair<int,long> pil;
typedef pair<long,int> pli;
typedef vector<vector<long long>> vvll;
typedef vector<vector<long>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<long> vl;
typedef vector<long long> vll;

#define emplace_back pb
const char el = '\n';

/*
Edge cases:


*/
void initializechunks(vector<bool>& hascut, vector<int>& chunksum,
int m,  int k, int j, bool& startsoutgood, vector<vector<int>>& g) {

    int temp=0;
    for (int i = 0; i<m; ++i) {
        temp += g[i][j];
        // cout<<"added g["<<i<<"]["<<j<<"]="<<g[i][j]<<" to acc"<<el;

        if (hascut[i]) {
            //break off;
            // cout<<"found break after row "<<i<<" and accumulator = "<<
            // temp<<el;
            chunksum[i] = temp;
            temp = 0;
        } else {
            //continue;
        }
    }
    startsoutgood = true;
    for (int i = 0; i<m; ++i) {
        if (chunksum[i]>k) {
            startsoutgood = false;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int m,n,k; cin>>m>>n>>k; cin.ignore();
    vector<vector<int>> g(m,vector<int>(n,0));
    for (int i= 0; i<m; ++i) {
        for (int j = 0; j<n; ++j) {
            char ch;
            cin>>ch;
            g[i][j]=(int)(ch-'0');
        }

    }

    // cout<<"board: "<<el;
    // for (auto row: g) {
    //     for (auto x: row) {
    //         cout<<x;
    //     }
    //     cout<<el;
    // }
    int twopow = 1;
    for (int i = 0; i<m-1; ++i) twopow*=2;
    //mk[i] = 1 means there IS  acut after the i-th row (zero-indexed);
    
    int recordlow = m-1+n-1;
    for (int mk = 0; mk<twopow; ++mk) {
        //given this mask,
        bitset<10> b(mk);
        // cout<<"MASK, "<<mk<<",  has "<<b.count()<<" cuts"<<el;
        vector<bool> hascut(m,false);
        int horcuts = 0;
        for (int i = 0; i<m-1; ++i) {

            hascut[i] = b[i];

            if (hascut[i]) {
                // cout<<"hor cut after row "<<i<<el;
                ++horcuts;
            }
        }
        hascut[m-1]=true;

        // cout<<"started out with "<<horcuts<<" horizontal cuts from mask "<<mk<<el;
        vector<int> chunksum(m,0);
        //chunksum[x] = the sum of 1s inside the division
        //say that there is  cut after j1; Then 
        //chunksum[j1] measures from the previous chunk up to and including
        //element j1;
        // so we need to do an extra one for chunksum[m-1] after the last cut;
        bool startsoutgood = true;
        initializechunks(hascut,chunksum,m,k,0,startsoutgood,g);
        if (!startsoutgood) {
            //go to next mask;
            // cout<<"already failed!"<<endl;
            continue;
        }


        // cout<<"hascuts = ";
        // for (auto x: hascut) cout<<x<<" ";
        // cout<<el;
        // cout<<"chunk sums started out as:  "<<el;
        // for (int i = 0; i<m; ++i) {
        //     if (hascut[i]) {
        //         cout<<chunksum[i]<<" ending at row "<<i<<el;            }
        // }

        int cuts = horcuts;
        // cout<<"cuts strts off = "<<cuts<<el;
        //greedily accumulate columns;
        for (int j = 1; j<n; ++j) {
            //decide whether a cut BEFORE col j is needed;
            if (!startsoutgood) {
                cuts += (m-1+n-1);
                break;

            }
            int temp = 0; 
            for (int i=0; i<m; ++i) {

                temp += g[i][j];

                if (hascut[i]) {
                    //add temp to this chunksum;
                    chunksum[i] += temp;
                    temp=0;
                    if (chunksum[i] > k) {
                        //cut
                        // cout<<"making cut before col "<<j<<" due to "
                        // " sum equals "<<chunksum[i]<<" ending at row "<<i<<el;
                        ++cuts;
                        // cout<<"cuts now = "<<cuts<<el;
                        // std::fill(chunksum.begin(),chunksum.end(),0);

                        initializechunks(hascut,chunksum,m,k,j,startsoutgood,g);
                        break;
                    }


                }
            }
        }
        //need to make sure the current sum, is ok;
        if (startsoutgood) recordlow = min(recordlow,cuts);

        // cout<<"record now "<<recordlow<<el;
    }
    // cout<<"answer:  "<<recordlow<<el;
    cout<<recordlow<<el;

}

Measured memory_bytes: 384