#include <bits/stdc++.h>
using namespace std;
int main(void) {
    ios_base::sync_with_stdio(false);
    int h, w, kg;
    cin >> h >> w >> kg;
    int grid[h][w];
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            char temp;
            cin >> temp;
            if (temp == '0')
                grid[i][j] = 0;
            else
                grid[i][j] = 1;
        }
    int gridt[h + 1][w + 1];
    memset(gridt, 0, sizeof(gridt));
    for (int i = 0; i < h; i++) {
        int curtotal = 0;
        for (int j = 0; j < w; j++) {
            curtotal += grid[i][j];
            if (i == 0 && j == 0) {
                gridt[i][j] = curtotal;
            } else if (i == 0) {
                gridt[i][j] = curtotal;
            } else {
                gridt[i][j] = curtotal + gridt[i - 1][j];
            }
        }
    }
    int bst = (h - 1) + (w - 1);
    for (int i = 0; i < (1 << (h + 1)); i++) {
        int cur_cut = 0;
        int last_wcut = 0, last_hcut = 0;
        bool cut[w];
        memset(cut, 0, sizeof(cut));
        bool fail = false;
        // cout<<"GO"<<i<<'\n';
        for (int k = 0; k < w; k++) {
            bool over = false;
            int curtotal = 0;
            last_hcut = 0;
            for (int j = 0; j < h; j++) {
                if ((1 << j) & i) {
                    last_hcut = j;
                }
                if (j == h - 1 || ((1 << (j + 1)) & i)) {
                    // cout<<j<<' '<<last_hcut<<'\n';
                    int cur;
                    if (last_hcut == 0 && last_wcut == 0) {
                        cur = gridt[j][k];
                    } else if (last_hcut == 0) {
                        cur = gridt[j][k] - gridt[j][last_wcut - 1];
                    } else if (last_wcut == 0) {
                        cur = gridt[j][k] - gridt[last_hcut - 1][k];
                    } else {
                        cur = gridt[j][k] - gridt[last_hcut - 1][k] -
                              gridt[j][last_wcut - 1] +
                              gridt[last_hcut - 1][last_wcut - 1];
                    }
                    if (cur > kg) {
                        cut[k] = true;
                        last_wcut = k;
                    }
                }
            }
            // for(int k = 0; k < w; k++)cout<<cut[k]<<' ';
            // cout<<"\n";
        }
        last_hcut = 0;
        for (int j = 0; j < h; j++) {
            if (((1 << j) & i)) {
                cur_cut++;
            }
        }
        for(int k = 0;k <w ;k++){
            if(cut[k]){
                cur_cut++;
            }
        }
        for (int j = 0; j < h; j++) {
            if (((1 << j) & i)) {
                last_hcut = j;
            }
            last_wcut = 0;
            for (int k = 0; k < w; k++) {
                int cur;
                if (cut[k]) {
                    last_wcut = k;
                }
                if (last_hcut == 0 && last_wcut == 0) {
                    cur = gridt[j][k];
                } else if (last_hcut == 0) {
                    cur = gridt[j][k] - gridt[j][last_wcut - 1];
                } else if (last_wcut == 0) {
                    cur = gridt[j][k] - gridt[last_hcut - 1][k];
                } else {
                    cur = gridt[j][k] - gridt[last_hcut - 1][k] -
                          gridt[j][last_wcut - 1] +
                          gridt[last_hcut - 1][last_wcut - 1];
                }
                // cout<<i<<' '<<j<<' '<<k<<'\n';
                // cout<<last_hcut<<' '<<last_wcut<<"\n";
                // cout<<cur<<'\n';
                if (cur > kg) {
                    fail = true;
                }
            }
            // for(int k = 0; k < w; k++)cout<<cut[k]<<' ';
            // cout<<"\n";
        }
        if (!fail) {
            // cout << i << '\n';
            // for (int z = 0; z < w; z++) {
            //     cout << cut[z] << ' ';
            // }
            // cout << '\n';
            // cout<<cur_cut<<'\n';
            bst = min(cur_cut, bst);
        }
    }
    cout << bst << '\n';
}

Measured memory_bytes: 384