Problem:
 Score : 500 points    Problem Statement We have a chocolate bar partitioned into H horizontal rows and W vertical columns of squares.  The square (i, j) at the i -th row from the top and the j -th column from the left is dark if S_{i,j} is 0 , and white if S_{i,j} is 1 .  We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.  How many times do we need to cut the bar so that every block after the cuts has K or less white squares?      Constraints  1 \leq H \leq 10  1 \leq W \leq 1000  1 \leq K \leq H \times W  S_{i,j} is 0 or 1 .         Input Input is given from Standard Input in the following format:  H  W  K  S_{1,1}S_{1,2}...S_{1,W}  :  S_{H,1}S_{H,2}...S_{H,W}       Output Print the number of minimum times the bar needs to be cut so that every block after the cuts has K or less white squares.        Sample Input 1 3 5 4
11100
10001
00111      Sample Output 1 2  For example, cutting between the 1 -st and 2 -nd rows and between the 3 -rd and 4 -th columns - as shown in the figure to the left - works.  Note that we cannot cut the bar in the ways shown in the two figures to the right.        Sample Input 2 3 5 8
11100
10001
00111      Sample Output 2 0  No cut is needed.       Sample Input 3 4 10 4
1110010010
1000101110
0011101001
1101000111      Sample Output 3 3

Solution (Python):
H, W, K = map(int, input().split())
S = [list(map(int, input())) for i in range(H)]

ret = W - 1 + H - 1

for i in range(1 << (H - 1)):
    sep = bin(i)[2:].rjust(H - 1, '0')[::-1]

    tile_idx = [0] * H
    cut = 0

    for j in range(H):
        tile_idx[j] = cut

        if j == H - 1:
            break

        if sep[j] == '1':
            cut += 1

    cnt_lst = [0] * (cut + 1)
    num_cnt = 0

    for w in range(W):
        col_new = [0] * (cut + 1)

        flag = False
        flag1 = False
        for h in range(H):
            if S[h][w] == 1:
                idx = tile_idx[h]
                col_new[idx] += 1

        for a in col_new:
            if a > K:
                flag1 = True
                break

        if flag1:
            break

        for k in range(cut + 1):
            if cnt_lst[k] + col_new[k] > K:
                num_cnt += 1
                for l in range(cut + 1):
                    cnt_lst[l] = col_new[l]

                flag = True
                break

        if not flag:
            for k in range(cut + 1):
                cnt_lst[k] += col_new[k]

    if not flag1:
        ret = min(ret, num_cnt + cut)


print(ret)

Solution (Python):
H,W,K = map(int,input().split())
C = [[int(i) for i in input()] for _ in range(H)]
ans = float("inf")

for i in range(1<<(H-1)):
    start = [0]
    end = []
    for j in range(H-1):
        if i & (1 << j):
            j += 1
            start.append(j)
            end.append(j)
    end.append(H)
    L = len(end)
    cnt = [0]*L
    dcnt = L-1
    fail = False
    for w in range(W):
        div = False
        idx = 0
        tmp = [0]*L
        for s,e in zip(start,end):
            for h in range(s,e): tmp[idx] += C[h][w]
            if tmp[idx] > K: 
                fail = True
                break
            if cnt[idx] + tmp[idx] > K:
                div = True
                cnt = tmp[:]
            else:
                cnt[idx] += tmp[idx]
            idx += 1
        if fail: break
        if div: dcnt += 1
    if fail: continue
    ans = min(dcnt,ans)

print(ans)

Solution (Python):
import itertools

H,W,K=map(int,input().split())
S=[input() for _ in range(H)]

ans=1e4 
for t in itertools.product([0,1],repeat=H-1):
    cnt=t.count(1)
    SW=[]
    tmp=[int(s) for s in S[0] ]
    
    for i, c in enumerate(t):
        if c:
            SW.append(tmp)
            tmp = [int(s) for s in S[i + 1]]
        else:
            tmp = [tmp[j] + int(S[i + 1][j]) for j in range(W)]
    SW.append(tmp)
    H_ = len(SW)
    sums = [0] * H_
    if max(itertools.chain.from_iterable(SW)) > K:
        continue
    for w in range(W):
        sumtmp = [sums[i] + SW[i][w] for i in range(H_)]
        if max(sumtmp) > K:
            cnt += 1
            sums = [SW[i][w] for i in range(H_)]
        else:
            sums = sumtmp
    ans = min(ans, cnt)
print(ans)

Solution (Python):
H,W,K=map(int,input().split())
S=[[int(x) for x in list(str(input()))] for _ in range(H)]
T=[[0]*(W+1) for x in range(H+1)]

def main():
  for h in range(H):
    for w in range(W):
      T[h][w]=T[h][w-1]+S[h][w]

  for h in range(1,H):
    for w in range(W):
      T[h][w]=T[h][w]+T[h-1][w]

  m=(H-1)*(W-1)
  for p in range(2**(H-1)):
    D=[x for x in range(H-1) if p&(2**x)!=0]+[H-1]
    c,b=0,-1
    f=False
    for w in range(W):
      u=-1
      for d in D:
        if T[d][w]-T[u][w]-T[d][b]+T[u][b]>K:
          if b==w-1:
            f=True
          c,b=c+1,w-1
          break
        u=d
      if f==True:
        break
    else:
      m=min(m,c+len(D)-1)
  print(m)
main()

Solution (Python):
H,W,K=map(int,input().split())
S=[[int(x) for x in list(str(input()))] for _ in range(H)]
T=[[0]*(W+1) for x in range(H+1)]

for h in range(H):
  for w in range(W):
    T[h][w]=T[h][w-1]+S[h][w]

for h in range(1,H):
  for w in range(W):
    T[h][w]=T[h][w]+T[h-1][w]

m=(H-1)*(W-1)
for p in range(2**(H-1)):
  D=[x for x in range(H-1) if p&(2**x)!=0]+[H-1]
  c,b=0,-1
  f=False
  for w in range(W):
    u=-1
    for d in D:
      if T[d][w]-T[u][w]-T[d][b]+T[u][b]>K:
        if b==w-1:
          f=True
        c,b=c+1,w-1
        break
      u=d
    if f==True:
      break
  else:
    m=min(m,c+len(D)-1)
print(m)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
from re import split
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy
import re

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

h, w, k = LI()
s = SRL(h)
ans = INF
for bits in range(2 ** (h - 1)):
    res = sum([int(j) for j in "{0:b}".format(bits)])
    div_cnt = res + 1
    cnt = [0] * div_cnt
    x = 0
    flg = 0
    while x < w:
        cur = 0
        for y in range(h):
            if s[y][x] == '1':
                cnt[cur] += 1
            if bits >> y & 1:
                cur += 1
        if max(cnt) > k:
            if flg == 0:
                res = INF
                break
            else:
                cnt = [0] * div_cnt
                flg = 0
                res += 1
        else:
            flg = 1
            x += 1
    ans = min(ans, res)


print(ans)

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w, k = na()
s = nsn(h)

ans = inf
for bits in range(2 ** (h - 1)):
    binf = "{0:b}".format(bits)
    res = sum([int(b) for b in binf])
    divcnt = res + 1
    cnt = [0] * divcnt
    flag = True
    j = 0
    while j < w:
        cur = 0
        for i in range(h):
            if (s[i][j] == '1'):
                cnt[cur] += 1
            if bits >> i & 1:
                cur += 1
        if max(cnt) > k:
            if flag:
                res = inf
                break
            res += 1
            for i in range(divcnt):
                cnt[i] = 0
            flag = True
        else:
            flag = False
            j += 1
    ans = min(ans, res)

print(ans)

Solution (Python):
h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*w for _ in range(h)]

def count(x1,y1,x2,y2): 
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

for i in range(h): 
  for j in range(w):
    if board[i][j] == '1':
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]

ans = 10**18
for i in range(2**(h-1)):
  cnt = 0
  list = []
  flag = format(i,'b')[::-1] 
  
  for j in range(len(flag)):
    if flag[j] == '1': 
      cnt += 1
      list.append(j)
  list.append(h-1)
  
  x1 = 0
  for x2 in range(w-1): 
    y1 = 0
    for y2 in list: 
      if count(x1,y1,x2,y2) > k: 
        cnt += 10**18
      if count(x1,y1,x2,y2) <= k and count(x1,y1,x2+1,y2) > k: 
        cnt += 1
        x1 = x2+1 
        break
      y1 = y2+1 
  y1 = 0
  for y2 in list:
    if count(x1,y1,w-1,y2) > k: 
      cnt += 10**18
      break
    y1 = y2+1
  ans = min(ans,cnt)
print(ans)

Solution (Python):
h,w,k=map(int,input().split())
board=[list(input()) for _ in range(h)]
acum=[[0]*w for _ in range(h)]

def count(x1,y1,x2,y2): 
  ret=acum[y2][x2]
  if x1!=0:
    ret-=acum[y2][x1-1]
  if y1!=0:
    ret-=acum[y1-1][x2]
  if x1!=0 and y1!=0:
    ret+=acum[y1-1][x1-1]
  return ret

for i in range(h): 
  for j in range(w):
    if board[i][j] == '1': 
      acum[i][j]+=1
    if i!=0:
      acum[i][j]+=acum[i-1][j]
    if j!=0:
      acum[i][j]+=acum[i][j-1]
    if i!=0 and j!=0:
      acum[i][j]-=acum[i-1][j-1]

ans = 10**18
for i in range(2**(h-1)):
  cnt = 0
  list = []
  flag = format(i,'b')[::-1]
  for j in range(len(flag)):
    if flag[j] == '1': 
      cnt += 1
      list.append(j)
  list.append(h-1)
  x1 = 0
  for x2 in range(w-1): 
    y1 = 0
    for y2 in list: 
      if count(x1,y1,x2,y2) > k: 
        cnt += 10**18
      if count(x1,y1,x2,y2) <= k and count(x1,y1,x2+1,y2) > k: 
        cnt += 1
        x1 = x2+1 
        break
      y1 = y2+1 
  y1 = 0
  for y2 in list:
    if count(x1,y1,w-1,y2) > k: 
      cnt += 10**18
      break
    y1 = y2+1
  ans = min(ans,cnt)
print(ans)

Solution (Python):
def main():
  from collections import Counter
  from collections import defaultdict
  from collections import deque
  from itertools import accumulate
  from itertools import combinations
  from itertools import permutations
  from itertools import product
  import sys
  sys.setrecursionlimit(10**6)
  readline = sys.stdin.readline
  ints = lambda: map(int, readline().split())
  floats = lambda: map(float, readline().split())
  lli = lambda I, J: [[0] * J for _ in range(I)]
  mod = 10**9+7

  h, w, k = ints()
  ans = h + w
  s = [list(map(int, input())) for _ in range(h)]
  for comb in product([False, True], repeat=h - 1):
    divs = 0
    a = [s[0][:]]
    for row, isd in zip(s[1:], comb):
      if isd:
        a += [row[:]]
        divs += 1
      else:
        for i in range(w):
          a[divs][i] += row[i]
    dh = divs + 1
    ta = [list(i) for i in zip(*a)]
    currow = ta[0]
    imp = False
    for row in ta[1:]:
      if any([i > k for i in currow]):
        imp = True
        break
      else:
        temp = [i + j for i, j in zip(currow, row)]
        if any([i > k for i in temp]):
          currow = row
          divs += 1
        else:
          currow = temp
    if not imp:
      ans = min(ans, divs)
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
def main():
  from itertools import product
  import sys
  sys.setrecursionlimit(10**6)
  readline = sys.stdin.readline
  ints = lambda: map(int, readline().split())
  floats = lambda: map(float, readline().split())
  lli = lambda I, J: [[0] * J for _ in range(I)]
  mod = 10**9+7

  h, w, k = ints()
  ans = h + w
  s = [list(map(int, input())) for _ in range(h)]
  for comb in product([False, True], repeat=h - 1):
    divs = 0
    a = [s[0][:]]
    for row, isd in zip(s[1:], comb):
      if isd:
        a += [row[:]]
        divs += 1
      else:
        for i in range(w):
          a[divs][i] += row[i]
    dh = divs + 1
    ta = [list(i) for i in zip(*a)]
    currow = ta[0]
    imp = False
    for row in ta[1:]:
      if any([i > k for i in currow]):
        imp = True
        break
      else:
        temp = [i + j for i, j in zip(currow, row)]
        if any([i > k for i in temp]):
          currow = row
          divs += 1
        else:
          currow = temp
    if not imp:
      ans = min(ans, divs)
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
def main():
  from collections import Counter
  from collections import defaultdict
  from collections import deque
  from itertools import accumulate
  from itertools import combinations
  from itertools import permutations
  from itertools import product
  import sys
  sys.setrecursionlimit(10**6)
  readline = sys.stdin.readline
  ints = lambda: map(int, readline().split())
  floats = lambda: map(float, readline().split())
  lli = lambda I, J: [[0] * J for _ in range(I)]
  mod = 10**9+7

  h, w, k = ints()
  ans = h + w
  s = [list(map(int, input())) for _ in range(h)]
  for comb in product([False, True], repeat=h - 1):
    divs = 0
    a = [s[0][:]]
    for row, isd in zip(s[1:], comb):
      if isd:
        a += [row[:]]
        divs += 1
      else:
        for i in range(w):
          a[divs][i] += row[i]
    dh = divs + 1
    ta = [list(i) for i in zip(*a)]
    currow = ta[0]
    imp = False
    for row in ta[1:]:
      if any([i > k for i in currow]):
        imp = True
        break
      else:
        temp = [i + j for i, j in zip(currow, row)]
        if any([i > k for i in temp]):
          currow = row
          divs += 1
        else:
          currow = temp
    if not imp:
      ans = min(ans, divs)
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):

import numpy as np

H, W, K = map(int, input().split())
S = np.zeros((H, W), dtype=np.int64)

ans = H+W

for i in range(H):
    S[i] = list(str(input()))

for m in range(1<<(H-1)):
    cut = bin(m).count('1')
    if cut >= ans:
        continue

    wp = np.zeros((cut+1, W), dtype=np.int64)
    wp[0] = S[0]
    c = 0
    for n in range(H-1):
        if m>>n&1:
            c += 1
        wp[c] += S[n+1]

    if np.count_nonzero(wp > K):
        continue

    wq = np.zeros((cut+1, ), dtype=np.int64)
    for j in range(W):
        wq += wp[:,j]
        if np.count_nonzero(wq > K):
            cut += 1
            wq = wp[:,j]

    ans = min(ans, cut)

print(ans)

Solution (Python):

import numpy as np

H, W, K = map(int, input().split())
S = np.zeros((H, W), dtype=np.int64)

ans = H+W

for i in range(H):
    S[i] = list(str(input()))

for m in range(2**(H-1)):
    wp = np.zeros((H, W), dtype=np.int64)
    wq = np.zeros((H, ), dtype=np.int64)
    wp[0] = S[0]
    cut = 0
    for n in range(H-1):
        if m>>n&1:
            cut += 1
        wp[cut] += S[n+1]

    if cut >= ans or np.count_nonzero(wp > K):
        continue

    for j in range(W):
        wq += wp[:,j]
        if np.count_nonzero(wq > K):
            cut += 1
            wq = wp[:,j]
    ans = min(ans, cut)

print(ans)

Solution (Python):

from itertools import combinations as combs

H,W,K = list(map(int, input().split()))
arr = []
for i in range(H):
  arr.append(list(map(int, list(input()))))

def cut_sum(arr, x1, x2, y):
  ret = 0
  for i in range(x1, x2):
    ret += arr[i][y]
  return ret

row_idxes = list(range(1,H))
min_val = float('inf')

for n_rows in range(H):
  for row_set in combs(row_idxes, n_rows):
    count = len(row_set)
    row_lines = [0] + list(row_set)+ [H]
    col1, col2 = 0, 1
    sums = [0] * (len(row_lines) - 1)
    while col2 <= W:
      row1 = 0
      for box, row2 in enumerate(row_lines[1:]):
        sums[box] += cut_sum(arr, row1, row2, col2-1)
        if sums[box] > K:
          if (col2 - col1) == 1:
            count = float('inf')
            break
          count += 1
          col1 = col2 - 1
          col2 -= 1
          sums = [0] * (len(row_lines) - 1)
          break
        row1 = row2
      if count >= min_val:
        break
      col2 += 1
    
    if min_val > count:
      min_val = count
print(min_val)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
from decimal import Decimal
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,K = inpl()
s = [input() for _ in range(n)]
res = INF
for pat in itertools.product([0,1], repeat=n-1):
    pat = list(pat) + [0]
    group = []
    tmp = []
    for i,j in enumerate(pat):
        tmp += [i]
        if j or i == n-1:
            group += [tmp]
            tmp = []
    
    ln = len(group)
    white = [[0]*ln for _ in range(m)]
    ccc = set()
    cnt = pat.count(1) 
    ok = True
    for i in range(m):
        for j,z in enumerate(group):
            for k in z:
                if s[k][i] == '1':
                    white[i][j] += 1
            if max(white[i]) > K:
                ok = False
                break
    if not ok: continue
    
    now = [0] * ln
    for i in range(m):
        ok = True
        for j in range(ln):
            if now[j] + white[i][j] > K:
                ok = False
                break
        if ok:
            for j in range(ln):
                now[j] += white[i][j]
        else:
            cnt += 1
            for j in range(ln):
                now[j] = white[i][j]
    res = min(res, cnt)
print(res)

Solution (Python):
import sys
input = sys.stdin.readline
H,W,K=map(int,input().split())
CO=[[0 for i in [0]*W] for j in [0]*H]
DO=[[0 for i in [0]*W] for j in [0]*H]
for i in range(H):
 C=input()
 for j in range(W):
  DO[i][j]=int(C[j])
CO[H-1]=DO[H-1]
F=1000000
for s in range(2**(H-1)):
 D=0
 E=0
 Sui=[0]*(H-1)
 for t in range(H-1):
  if ((s >> t) & 1):
   Sui[t]+=1
 for m in range(H-1):
  E+=Sui[m]
 for k in range(H-1):
  if Sui[k]==0:
   for i in range(W):
    CO[H-k-2][i]=DO[H-k-2][i]+CO[H-k-1][i]
  else:
   for i in range(W):
    CO[H-k-2][i]=DO[H-k-2][i]
 lst=[0]*H
 for h in range(W):
  c=max(CO[x][h] for x in range(H))
  d=max(lst[y]+CO[y][h] for y in range(H))
  if c>K:
   E=1000000
   break
  elif d>K:
   D+=1
   lst=[0]*H
  for z in range(H):
   lst[z]+=CO[z][h]
 F=min(F,D+E)
print(F)

Solution (Python):
h,w,lim = map(int,input().split())
S = []
ans = 10**10
for i in range(h):
    S.append(input())
for i in range(2**(h-1)):
    bit = ''
    cur = 1
    for j in range(h-1):
        if i&cur != 0:
            bit = '1'+bit
        else:
            bit = '0'+bit
        cur *= 2
    group = []
    if i == 0:
        group = [[i for i in range(h)]]
    else:
        div = []
        for j in range(len(bit)):
            if bit[j] == '0':
                div.append(j)
            else:
                div.append(j)
                group.append(div)
                div = []
        div.append(j+1)
        if len(div) != 0:
            group.append(div)
    num = [0]*len(group)
    cur = len(group)-1
    flag1 = True
    for j in range(w):
        next = [0]*len(group)
        flag2 = True
        for k in range(len(group)):
            plus = 0
            for l in range(len(group[k])):
                if S[group[k][l]][j] == '1':
                    plus += 1
            if plus > lim:
                flag1 = False
                break
            elif plus+num[k] > lim:
                flag2 = False
                next[k] += plus
            else:
                next[k] += plus
        if flag1 == False:
            break
        else:
            if flag2 == False:
                cur += 1
                num = next
            else:
                for k in range(len(group)):
                    num[k] += next[k]
    if flag1:
        ans = min(ans, cur)
print(ans)

Solution (Python):
H,W,K = map(int,input().split())
S = [[int(i) for i in input()] for _ in range(H)]
ans = float("inf")


for i in range(2**(H-1)):
    start = [0]
    end = []
    for j in range(H-1):
        if i >> j & 1 == 1:
            j += 1
            start.append(j)
            end.append(j)
    end.append(H)
    L = len(end)
    
    divcnt = L-1
    
    wcnt = [0]*L
    
    tmp = [0]*L
    for w in range(W):
        
        flag = False
        for idx in range(L):
            cnt = 0
            for h in range(start[idx],end[idx]):
                cnt += S[h][w]
                if cnt > K: break
            else:
                tmp[idx] = cnt
                wcnt[idx] += cnt
                if wcnt[idx] > K: flag = True
                continue
            break
        else:
            if flag:
                
                wcnt = tmp[:]
                divcnt += 1
            continue
        break
    else:
        ans = min(ans,divcnt)

print(ans)

Solution (Python):

import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    num = g - 1

    if num >= ans:
        continue

    c = [[0] * W for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    now = [0 for _ in range(g)]


    def add(j):
        for i in range(g):
            now[i] += c[i][j]

        for i in range(g):
            if now[i] > K:
                return False

        return True


    for j in range(W):
        if not add(j):
            num += 1
            if num >= ans:
                continue
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)

Solution (Python):

import sys

ans = sys.maxsize
H, W, K = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(1 << (H - 1)):
    g = 0
    ids = [-1 for _ in range(H)]
    for i in range(H):
        ids[i] = g
        if (h >> i) & 1:
            g += 1

    g += 1
    c = [[0 for _ in range(W)] for _ in range(g)]
    for i in range(H):
        for j in range(W):
            c[ids[i]][j] = c[ids[i]][j] + (s[i][j] == '1')

    num = g - 1
    now = [0 for _ in range(g)]


    def add(j):
        for i in range(g):
            now[i] += c[i][j]

        for i in range(g):
            if now[i] > K:
                return False

        return True

    if num >= ans:
        continue

    for j in range(W):
        if not add(j):
            num += 1
            if num >= ans:
                continue
            now = [0 for _ in range(g)]
            if not add(j):
                num = sys.maxsize
                break

    ans = min(ans, num)

print(ans)

Solution (Python):
h,w,k=[int(j) for j in input().split()]
s=[list(map(int,list(input()))) for i in range(h)]
import itertools
s=tuple(itertools.chain(*zip(*s)))
ans=10**18
for i in range(1<<(h-1)):
    dp=list(s)
    for j in range(h-1):
        if i&(1<<j):
            for n in range(0,h*w,h):
                dp[n+j+1]+=dp[n+j]
    tmp=h-1-bin(i).count("1")
    b=False
    for n in range(0,h*w,h):
        if any(dp[n+j]>k for j in range(h)):
            tmp=10**18
            break
        if n+h==h*w:
            ans=min(ans,tmp)
            tmp=10**18
            break
        if any(dp[n+j]+dp[n+j+h]>k for j in range(h)):
            tmp+=1
            continue
        for j in range(h):
            dp[n+j+h]+=dp[n+j]
    ans=min(ans,tmp)
print(ans)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,w,k = m()

s = []

for i in range(h):
    s.append(list(map(int,input()[:-1])))

st = [0 for i in range(h)]
dp = [[0,0] for i in range(h)]
ans = mod

for po in range(2 << h):
    de = 0
    tm = 0
    for j in range(h):
        dp[j][0] = 0
        dp[j][1] = 0
    for j in range(h):
        if j == 0:
            st[0] = 0
        else:
            a = (po>>j)&1
            b = (po>>(j-1))&1
            if a != b:
                de += 1
            st[j] = de
            
    tm += de
    
    for kp in range(w):
        fl = 0
        for kk in range(h):
            if s[kk][kp] == 1:
                dp[st[kk]][1] += 1
        if all(dp[x][0] + dp[x][1] <= k for x in range(h)):
            for kk in range(h):
                dp[kk][0] += dp[kk][1]
                dp[kk][1] = 0
        else:
            tm += 1
            for kk in range(h):
                if dp[kk][0] > k:
                    fl = 1
                    break
                dp[kk][0] = dp[kk][1]
                dp[kk][1] = 0
        if fl:
            break
    else:
        ans = min(tm,ans)
print(ans)

Solution (Python):
from itertools import accumulate


H, W, K = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]


accs = [[0]+list(accumulate(l)) for l in zip(*S)]

ans = float('inf')

for i in range(1 << H - 1):
    parts = []
    cuts = 0
    for k in range(H - 1):
        if i & (1 << k):
            cuts += 1
            parts.append(k+1)
    
    parts.append(H)
    cts = [0]*len(parts)
    for j in range(W):
        prev = 0
        flag1 = False
        for idx, p in enumerate(parts):
            c = accs[j][p] - accs[j][prev]
            cts[idx] += c
            if cts[idx] > K:
                flag1 = True
                break
            prev = p
        if flag1:
            cuts += 1
            prev = 0
            flag2 = False
            for idx, p in enumerate(parts):
                c = accs[j][p] - accs[j][prev]
                if c > K:
                    flag2 = True
                    break
                cts[idx] = c
                prev = p
            if flag2:
                break
    else:
        ans = ans if ans < cuts else cuts

print(ans)

Solution (Python):
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

INF = 10 ** 20
ans = INF
for div in range(1 << (h - 1)):
    id = []
    g = 0
    for i in range(h):
        id.append(g)
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(w)] for _ in range(g)]
    for i in range(h):
    	for j in range(w):
            c[id[i]][j] += (s[i][j] == "1")

    if max([max(l) for l in c]) > k:
        continue

    tmp_ans = g - 1
    now = [0] * g

    for j in range(w):
        for i in range(g):
            now[i] += c[i][j]
            if now[i] > k:
                tmp_ans += 1
                now = [c[gi][j] for gi in range(g)]
                break

    ans = min(ans, tmp_ans)

print(ans)

Solution (Python):
H,W,K = map(int,input().split())

import itertools
from collections import defaultdict
ZO = [0,1]

CHOCO = []
for i in range(H):
    s = input()
    CHOCO.append(s)

ans = 10**16
C = 0

for i in itertools.product(ZO,repeat = H-1):
    saki = 0
    To = defaultdict(int)
    To[0] = saki
    for j in range(H-1):
        if i[j]==0:
            To[j+1] = saki
        else:
            saki += 1
            To[j+1] = saki
    tmpans = saki
    
    NowWhite = [0]*(saki+1)
    preW = 0
    for w in range(W):
        h = 0
        while 1:
            C+= 1
            
            
              
            if CHOCO[h][w] == '1':
                NowWhite[To[h]] += 1
                if NowWhite[To[h]] > K:
                    
                    tmpans += 1
                    NowWhite = [0]*(saki+1)
                    h = -1
                    if preW==w:
                        tmpans += 10**16
                        break
                    preW = w
            if h==H-1:
                
                break
            h += 1
    ans = min(ans,tmpans)
print(ans)

Solution (Python):
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

INF = 10 ** 20
ans = INF
for div in range(1 << (h - 1)):
    id = []
    g = 0
    for i in range(h):
        id.append(g)
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(w)] for _ in range(g)]
    for i in range(h):
    	for j in range(w):
            c[id[i]][j] += (s[i][j] == "1")

    tmp_ans = g - 1
    now = [0] * g

    def add(j):
        for i in range(g):
            now[i] += c[i][j]
            if now[i] > k:
                return False
        return True

    for j in range(w):
        if not add(j):
            tmp_ans += 1
            now = [0] * g
            if not add(j):
                tmp_ans = INF
                break

    
    
    
    
    
    
    
    
    
    
    
    
    
    

    ans = min(ans, tmp_ans)

print(ans)

Solution (Python):
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

INF = 10 ** 20
ans = INF
for div in range(1 << (h - 1)):
    id = []
    g = 0
    for i in range(h):
        id.append(g)
        if div >> i & 1:
            g += 1
    g += 1

    c = [[0 for _ in range(w)] for _ in range(g)]
    for i in range(h):
    	for j in range(w):
            c[id[i]][j] += (s[i][j] == "1")

    tmp_ans = g - 1
    now = [0] * g

    def add(j):
        for i in range(g):
            now[i] += c[i][j]
        for i in range(g):
            if now[i] > k:
                return False
        return True

    for j in range(w):
        if not add(j):
            tmp_ans += 1
            now = [0] * g
            if not add(j):
                tmp_ans = INF
                break

    
    
    
    
    
    
    
    
    
    
    
    
    
    

    ans = min(ans, tmp_ans)

print(ans)