#include <bits/stdc++.h>
using namespace std;
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define all(x) ((x).begin()),((x).end())
using pii = pair <int, int>;
#define INF 0x7f7f7f7f7f7f7f7f
const bool debug = 0;

int choco[12][1010];
int h, w, k;
int presum[12][1010];
int linearpresum[12][1010];
int ans;
void print()
{
    for (int i = 0; i<=10; i++)
    {
        for (int j = 0; j<=10; j++)
        {
            printf("%d ",presum[i][j]);
        }
        printf("\n");
    }
}
inline int rangesum(int h1, int h2, int c1, int c2, bool pt = false)
{
    if (pt)
    {
        printf("H : %d ~ %d, C : %d ~ %d\n",h1,h2,c1,c2);
        printf("%d - %d - %d + %d\n",presum[h2][c2],presum[h1-1][c2],presum[h2][c1-1],presum[h1-1][c1-1]);
    }
    return presum[h2][c2]-presum[h1-1][c2]-presum[h2][c1-1]+presum[h1-1][c1-1];
}
int32_t main()
{
    scanf("%d %d %d",&h,&w,&k);
    for (int i = 1; i<=h; i++)
        for (int j = 1; j<=w; j++)
            scanf("%1d",&choco[i][j]);
        ans = h+w;
    for (int i = 1; i<=10; i++)
    {
        for (int j = 1; j<=1000; j++)
            linearpresum[i][j] = linearpresum[i][j-1]+choco[i][j];
    }
    for (int i = 1; i<=10; i++)
        for (int j = 1; j<=1000; j++)
            presum[i][j] = presum[i-1][j]+linearpresum[i][j];
    for (int i = 0; i<(1<<(h-1)); i++)
    {
        int cut = i;
        vector <int> cutplace;
        cutplace.push_back(0);
        for (int j = 0; j<(h-1); j++)
        {
            if (cut & (1<<j))
                cutplace.push_back(j+1);
        }
        cutplace.push_back(10);
        int req_cut = cutplace.size()-2;
        int pieces = cutplace.size()-1;
        int cur = 1;
        int last = 0;
        if (debug)
        {
            printf("Trying with ");
            for (auto it:cutplace)
            {
                printf("%d ",it);
            }
            printf("\n");
        }
        vector <int> piece(pieces+2, 0);
        while(last <= w)
        {
            if (debug)
                printf("Last cut = %d, current check = %d\n",last,cur);
            bool flag = 1;
            for (int t = 1; t<=pieces; t++)
            {
                int u = rangesum(cutplace[t-1]+1,cutplace[t],last+1,cur);
                if (debug)
                {
                    printf("Piece [%d, %d] ~ [%d, %d] = %d\n",cutplace[t-1]+1,cutplace[t],last+1,cur,u);
                }
                if (u <= k)
                    piece[t] = u;
                else
                {
                    if (debug)
                    {
                        printf("Unable to fit ");
                        printf("Piece [%d, %d] ~ [%d, %d] = %d\n",cutplace[t-1]+1,cutplace[t],last+1,cur,u);
                    }
                    last = cur-1;
                    fill(all(piece), 0);
                    req_cut++;
                    if (rangesum(cutplace[t-1]+1, cutplace[t], cur, cur)>k)
                        goto deadcut;
                    flag = 0;
                }
            }
            if (flag)
                cur++;
            if (cur > w)
                break;
        }
        if (debug)
        {
            printf("Finished with %d cut\n",req_cut);
        }
        ans = min(ans, req_cut);
        deadcut:
        continue;
    }
    cout << ans << '\n';
}

Measured memory_bytes: 384