def main():

  h,*s=open(0)

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

  s=[list(map(int,t[:w]))for t in s]

  m=9e9

  for i in range(1<<h-1):

    t=[]

    b=v=l=0

    for j in range(h):

      if i>>j&1:

        t+=list(map(sum,list(zip(*s[b:j+1])))),

        b=j+1

        l+=1

    t+=list(map(sum,list(zip(*s[b:])))),

    l+=1

    c=[0]*l

    for i in range(w):

      f=g=0

      u=[]

      for j,d in enumerate(t):

        d=d.__next__()

        u+=d,

        if d>k:

          g=1

          break

        c[j]+=d

        f|=c[j]>k

      else:

        if f:

          c=u

          v+=1

      if g:break

    else:

      if v+l-1<m:m=v+l-1

  print(m)

main()
r=range

h,*s=open(0)

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

m=9e9

for i in r(1<<h-1):

  t,v,l=[],-1,1

  for j in r(h):

    if i>>j&1:

      t+=j+1,

      l+=1

  t+=h,

  c=[0]*l

  for i in r(w):

    b=f=g=0

    u=[]

    for j in r(l):

      d,b=sum(s[j][i]=='1'for j in r(b,t[j])),t[j]

      u+=d,

      if d>k:

        g=1

        break

      c[j]+=d

      f|=c[j]>k

    else:

      v+=f

      if f:c=u

    if g:break

  else:m=min(m,v+l)

print(m)
def main():
    h, *s = open(0)
    h, w, k = list(map(int, h.split()))
    s = [list(map(int, t[:w])) for t in s]
    m = 9e9
    for i in range(1 << h - 1):
        t = []
        b = v = l = 0
        for j in range(h):
            if i >> j & 1:
                t += (list(map(sum, list(zip(*s[b : j + 1])))),)
                b = j + 1
                l += 1
        t += (list(map(sum, list(zip(*s[b:])))),)
        l += 1
        c = [0] * l
        for i in range(w):
            f = g = 0
            u = []
            for j, d in enumerate(t):
                d = d.__next__()
                u += (d,)
                if d > k:
                    g = 1
                    break
                c[j] += d
                f |= c[j] > k
            else:
                if f:
                    c = u
                    v += 1
            if g:
                break
        else:
            if v + l - 1 < m:
                m = v + l - 1
    print(m)


main()

r = range
h, *s = open(0)
h, w, k = list(map(int, h.split()))
m = 9e9
for i in r(1 << h - 1):
    t, v, l = [], -1, 1
    for j in r(h):
        if i >> j & 1:
            t += (j + 1,)
            l += 1
    t += (h,)
    c = [0] * l
    for i in r(w):
        b = f = g = 0
        u = []
        for j in r(l):
            d, b = sum(s[j][i] == "1" for j in r(b, t[j])), t[j]
            u += (d,)
            if d > k:
                g = 1
                break
            c[j] += d
            f |= c[j] > k
        else:
            v += f
            if f:
                c = u
        if g:
            break
    else:
        m = min(m, v + l)
print(m)

-def main(): -    h, *s = open(0) -    h, w, k = list(map(int, h.split())) -    s = [list(map(int, t[:w])) for t in s] -    m = 9e9 -    for i in range(1 << h - 1): -        t = [] -        b = v = l = 0 -        for j in range(h): -            if i >> j & 1: -                t += (list(map(sum, list(zip(*s[b : j + 1])))),) -                b = j + 1 -                l += 1 -        t += (list(map(sum, list(zip(*s[b:])))),) -        l += 1 -        c = [0] * l -        for i in range(w): -            f = g = 0 -            u = [] -            for j, d in enumerate(t): -                d = d.__next__() -                u += (d,) -                if d > k: -                    g = 1 -                    break -                c[j] += d -                f |= c[j] > k -            else: -                if f: -                    c = u -                    v += 1 -            if g: +r = range +h, *s = open(0) +h, w, k = list(map(int, h.split())) +m = 9e9 +for i in r(1 << h - 1): +    t, v, l = [], -1, 1 +    for j in r(h): +        if i >> j & 1: +            t += (j + 1,) +            l += 1 +    t += (h,) +    c = [0] * l +    for i in r(w): +        b = f = g = 0 +        u = [] +        for j in r(l): +            d, b = sum(s[j][i] == "1" for j in r(b, t[j])), t[j] +            u += (d,) +            if d > k: +                g = 1 +            c[j] += d +            f |= c[j] > k -            if v + l - 1 < m: -                m = v + l - 1 -    print(m) - - -main() +            v += f +            if f: +                c = u +        if g: +            break +    else: +        m = min(m, v + l) +print(m)