h,w,k=list(map(int,input().split()))

g=[[int(c) for c in eval(input())] for _ in range(h)]

s=[[0]*(w+1) for _ in range(h+1)]

for i in range(h):

  for j in range(w):

    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]

ssum=lambda u,d,l,r:s[d][r]-s[u][r]-s[d][l]+s[u][l]

a=h+w

for i in range(2**(h-1)):

  e=[]

  u=d=ch=0

  for j in range(h):

    d+=1

    if i>>j&1<1:

      e+=[(u,d)]

      if d<h:

        ch+=1

        u=d

  l=r=cw=0

  while r<w:

    if max(ssum(u,d,l,r+1) for u,d in e)>k:

      if r==l: break

      cw+=1

      l=r

    r+=1

  else:

    a=min(a,ch+cw)

print(a)
f=range

h,w,k=list(map(int,input().split()))

g=[[int(i) for i in eval(input())] for _ in f(h)]

s=[[0]*-~w for _ in f(h+1)]

for i in f(h):

  for j in f(w):

    s[i+1][j+1]=s[i+1][j]+s[i][j+1]+g[i][j]-s[i][j]

a=h+w

for i in f(2**~-h):

  u=d=l=r=c=0

  e=[]

  while d<h:

    d+=1

    if i>>d-1&1: e+=[(u,d)]; c+=1; u=d

  e+=[(u,h)]

  while r<w:

    if max(s[d][r+1]-s[u][r+1]-s[d][l]+s[u][l] for u,d in e)>k:

      if r==l: break

      c+=1; l=r

    r+=1

  else: a=min(a,c)

print(a)
h, w, k = list(map(int, input().split()))
g = [[int(c) for c in eval(input())] for _ in range(h)]
s = [[0] * (w + 1) for _ in range(h + 1)]
for i in range(h):
    for j in range(w):
        s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] + g[i][j] - s[i][j]
ssum = lambda u, d, l, r: s[d][r] - s[u][r] - s[d][l] + s[u][l]
a = h + w
for i in range(2 ** (h - 1)):
    e = []
    u = d = ch = 0
    for j in range(h):
        d += 1
        if i >> j & 1 < 1:
            e += [(u, d)]
            if d < h:
                ch += 1
                u = d
    l = r = cw = 0
    while r < w:
        if max(ssum(u, d, l, r + 1) for u, d in e) > k:
            if r == l:
                break
            cw += 1
            l = r
        r += 1
    else:
        a = min(a, ch + cw)
print(a)

f = range
h, w, k = list(map(int, input().split()))
g = [[int(i) for i in eval(input())] for _ in f(h)]
s = [[0] * -~w for _ in f(h + 1)]
for i in f(h):
    for j in f(w):
        s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] + g[i][j] - s[i][j]
a = h + w
for i in f(2 ** ~-h):
    u = d = l = r = c = 0
    e = []
    while d < h:
        d += 1
        if i >> d - 1 & 1:
            e += [(u, d)]
            c += 1
            u = d
    e += [(u, h)]
    while r < w:
        if max(s[d][r + 1] - s[u][r + 1] - s[d][l] + s[u][l] for u, d in e) > k:
            if r == l:
                break
            c += 1
            l = r
        r += 1
    else:
        a = min(a, c)
print(a)

+f = range -g = [[int(c) for c in eval(input())] for _ in range(h)] -s = [[0] * (w + 1) for _ in range(h + 1)] -for i in range(h): -    for j in range(w): +g = [[int(i) for i in eval(input())] for _ in f(h)] +s = [[0] * -~w for _ in f(h + 1)] +for i in f(h): +    for j in f(w): -ssum = lambda u, d, l, r: s[d][r] - s[u][r] - s[d][l] + s[u][l] -for i in range(2 ** (h - 1)): +for i in f(2 ** ~-h): +    u = d = l = r = c = 0 -    u = d = ch = 0 -    for j in range(h): +    while d < h: -        if i >> j & 1 < 1: +        if i >> d - 1 & 1: -            if d < h: -                ch += 1 -                u = d -    l = r = cw = 0 +            c += 1 +            u = d +    e += [(u, h)] -        if max(ssum(u, d, l, r + 1) for u, d in e) > k: +        if max(s[d][r + 1] - s[u][r + 1] - s[d][l] + s[u][l] for u, d in e) > k: -            cw += 1 +            c += 1 -        a = min(a, ch + cw) +        a = min(a, c)