import itertools

H, W, K = list(map(int, input().split()))



S = [0]*H

for i in range(H):

  S[i] = eval(input())

Sdivs = []

mcnt = 1100

for b in itertools.product([0, 1], repeat=H-1):

  start = 0

  end = 1

  Sdivs=[]

  for a in b:

    if a==1:

      Sdivs.append(S[start:end])

      start = end

    end += 1

  Sdivs.append(S[start:end])

  cnt = sum(b)

  #print(b,cnt,Sdivs)

  ones_cum = [0]*len(Sdivs)

  mark1,mark2 = True,True

  ws = [0]

  w = 1

  while w<W+1 and mark2:

    for i,Sdiv in enumerate(Sdivs):

      #print(w,ws)

      for s in Sdiv:

        ones_cum[i] += s[w-1]=='1'

      if ones_cum[i] > K:

        #print(i,w,ones_cum[i])

        mark1 = False

        if w-1 == ws[-1]:

          #print(w-1)

          mark2 = False

          break

        ws.append(w-1)

        w -= 1

        break

    if mark1 == False:

      mark1 = True

      ones_cum = [0]*len(Sdivs)

    w+=1

  #print(cnt,mark2)

  if mark2 == False:

    continue

  cnt += len(ws)-1

  #print(cnt)

  mcnt = min(mcnt,cnt)

print(mcnt)
from itertools import groupby, accumulate, product, permutations, combinations

def solve():

    H, W, K = list(map(int, input().split()))

    S = [eval(input()) for _ in range(H)]

    cum = [[0]*(W+1) for _ in range(H+1)]

    for i in range(1,H+1):

        for j in range(1,W+1):

            cum[i][j]=cum[i-1][j]+cum[i][j-1]-cum[i-1][j-1]+int(S[i-1][j-1])

    ans = 2000

    for p in product([0,1],repeat=H-1):

        line = [0]

        p = list(p)

        cnt = sum(p)

        for i in range(1,H):

            if p[i-1]==1:

                line.append(i)

        line.append(H)

        w_s = 0

        w_e = 1

        b = False

        while w_e <= W:

            for i in range(len(line)-1):

                h_s = line[i]

                h_e = line[i+1]

                white = cum[h_e][w_e]+cum[h_s][w_s]-cum[h_e][w_s]-cum[h_s][w_e]

                if white > K:

                    if w_e == w_s+1:

                        b = True

                        break

                    else:

                        w_s = w_e-1

                        cnt += 1

                        break

            if b==True:

                break

            w_e += 1

        else:

            ans = min(ans,cnt)

    return ans

print((solve()))
import itertools

H, W, K = list(map(int, input().split()))
S = [0] * H
for i in range(H):
    S[i] = eval(input())
Sdivs = []
mcnt = 1100
for b in itertools.product([0, 1], repeat=H - 1):
    start = 0
    end = 1
    Sdivs = []
    for a in b:
        if a == 1:
            Sdivs.append(S[start:end])
            start = end
        end += 1
    Sdivs.append(S[start:end])
    cnt = sum(b)
    # print(b,cnt,Sdivs)
    ones_cum = [0] * len(Sdivs)
    mark1, mark2 = True, True
    ws = [0]
    w = 1
    while w < W + 1 and mark2:
        for i, Sdiv in enumerate(Sdivs):
            # print(w,ws)
            for s in Sdiv:
                ones_cum[i] += s[w - 1] == "1"
            if ones_cum[i] > K:
                # print(i,w,ones_cum[i])
                mark1 = False
                if w - 1 == ws[-1]:
                    # print(w-1)
                    mark2 = False
                    break
                ws.append(w - 1)
                w -= 1
                break
        if mark1 == False:
            mark1 = True
            ones_cum = [0] * len(Sdivs)
        w += 1
    # print(cnt,mark2)
    if mark2 == False:
        continue
    cnt += len(ws) - 1
    # print(cnt)
    mcnt = min(mcnt, cnt)
print(mcnt)

from itertools import groupby, accumulate, product, permutations, combinations


def solve():
    H, W, K = list(map(int, input().split()))
    S = [eval(input()) for _ in range(H)]
    cum = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            cum[i][j] = (
                cum[i - 1][j] + cum[i][j - 1] - cum[i - 1][j - 1] + int(S[i - 1][j - 1])
            )
    ans = 2000
    for p in product([0, 1], repeat=H - 1):
        line = [0]
        p = list(p)
        cnt = sum(p)
        for i in range(1, H):
            if p[i - 1] == 1:
                line.append(i)
        line.append(H)
        w_s = 0
        w_e = 1
        b = False
        while w_e <= W:
            for i in range(len(line) - 1):
                h_s = line[i]
                h_e = line[i + 1]
                white = cum[h_e][w_e] + cum[h_s][w_s] - cum[h_e][w_s] - cum[h_s][w_e]
                if white > K:
                    if w_e == w_s + 1:
                        b = True
                        break
                    else:
                        w_s = w_e - 1
                        cnt += 1
                        break
            if b == True:
                break
            w_e += 1
        else:
            ans = min(ans, cnt)
    return ans


print((solve()))

-import itertools +from itertools import groupby, accumulate, product, permutations, combinations -H, W, K = list(map(int, input().split())) -S = [0] * H -for i in range(H): -    S[i] = eval(input()) -Sdivs = [] -mcnt = 1100 -for b in itertools.product([0, 1], repeat=H - 1): -    start = 0 -    end = 1 -    Sdivs = [] -    for a in b: -        if a == 1: -            Sdivs.append(S[start:end]) -            start = end -        end += 1 -    Sdivs.append(S[start:end]) -    cnt = sum(b) -    # print(b,cnt,Sdivs) -    ones_cum = [0] * len(Sdivs) -    mark1, mark2 = True, True -    ws = [0] -    w = 1 -    while w < W + 1 and mark2: -        for i, Sdiv in enumerate(Sdivs): -            # print(w,ws) -            for s in Sdiv: -                ones_cum[i] += s[w - 1] == "1" -            if ones_cum[i] > K: -                # print(i,w,ones_cum[i]) -                mark1 = False -                if w - 1 == ws[-1]: -                    # print(w-1) -                    mark2 = False -                    break -                ws.append(w - 1) -                w -= 1 + +def solve(): +    H, W, K = list(map(int, input().split())) +    S = [eval(input()) for _ in range(H)] +    cum = [[0] * (W + 1) for _ in range(H + 1)] +    for i in range(1, H + 1): +        for j in range(1, W + 1): +            cum[i][j] = ( +                cum[i - 1][j] + cum[i][j - 1] - cum[i - 1][j - 1] + int(S[i - 1][j - 1]) +            ) +    ans = 2000 +    for p in product([0, 1], repeat=H - 1): +        line = [0] +        p = list(p) +        cnt = sum(p) +        for i in range(1, H): +            if p[i - 1] == 1: +                line.append(i) +        line.append(H) +        w_s = 0 +        w_e = 1 +        b = False +        while w_e <= W: +            for i in range(len(line) - 1): +                h_s = line[i] +                h_e = line[i + 1] +                white = cum[h_e][w_e] + cum[h_s][w_s] - cum[h_e][w_s] - cum[h_s][w_e] +                if white > K: +                    if w_e == w_s + 1: +                        b = True +                        break +                    else: +                        w_s = w_e - 1 +                        cnt += 1 +                        break +            if b == True: -        if mark1 == False: -            mark1 = True -            ones_cum = [0] * len(Sdivs) -        w += 1 -    # print(cnt,mark2) -    if mark2 == False: -        continue -    cnt += len(ws) - 1 -    # print(cnt) -    mcnt = min(mcnt, cnt) -print(mcnt) +            w_e += 1 +        else: +            ans = min(ans, cnt) +    return ans + + +print((solve()))