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-----
3 5 4
11100
10001
00111

-----Sample Output-----
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.

Difficulty: interview

Starter code:

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

choco = [list(map(int, list(input()) )) for i in range(h)]

choco_cumsum = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    choco_cumsum[i][0] = choco[i][0]
    for j in range(1, w):
        choco_cumsum[i][j] = choco_cumsum[i][j-1] + choco[i][j]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    # 上位ビットが上側。1が切る、0が切らない
    num_cut_init = bin(h_cut).count("1") # 立っているビットの個数
    num_cut = num_cut_init
    w_last_cot_pos = -1
    valid = True

    temp_list = [0] * (num_cut_init + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        # print('idx', 2 ** (-i+h-1) )
        if h_cut & (2 ** (-i+h-1) ):
            idx += 1
        # idx += h_cut & (2 ** (h-1) - i)
        temp_dict[i] = idx
    # print(temp_dict)

    iw = 0
    while iw < w:

        for ih in range(h):
            temp_list[temp_dict[ih]] += choco[ih][iw]
        # print(iw, temp_list)

        condition = max(temp_list) > k
        if condition:
            if w_last_cot_pos < iw-1:
                # もしそこで切ってkを超えるなら、その手前で切る
                num_cut += 1
                w_last_cot_pos = iw - 1
                temp_list = [0] * (num_cut_init + 1)
                # print('iw: ', iw, 'last: ', w_last_cot_pos)

            else:
                # 1つしか動かしてない場合は土台無理なので次のh_cutに
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    # print(num_cut)

print(ans)


from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for si, bi in zip(s[1:], BIT):
        if bi == 1:
            LIST.append(tmp)
            tmp = si[:]
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, si)]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    COST, cnt = 0, [li[0] for li in LIST]
    if any(num > k for num in cnt):
        return h * w
    for j in range(1, w):
        tmp = [t + li[j] for t, li in zip(cnt, LIST)]
        if any(num > k for num in tmp):
            COST += 1
            cnt = [li[j] for li in LIST]
        else:
            cnt = tmp[:]
    return COST


h, w, k = list(map(int, input().split()))
s = [[int(sij) for sij in input()] for _ in range(h)]

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)


import sys
from itertools import product

read = sys.stdin.read
readline = sys.stdin.readline

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

answer = 10 ** 10
for i in product((0, 1), repeat=H - 1):
    cnt = sum(i)
    if cnt >= answer:
        continue
    cuts = []
    cuts.append(S[0].copy())
    for j in range(H - 1):
        if i[j] == 1:
            cuts.append(S[j + 1].copy())
        else:
            tmp1 = cuts[-1]
            tmp2 = S[j + 1]
            for k in range(W):
                tmp1[k] += tmp2[k]
    for j in cuts:
        if any(k > K for k in j):
            break
    else:
        h = len(cuts)
        tmp = [0] * h

        for j in range(W):
            for k in range(h):
                tmp[k] += cuts[k][j]
            for k in tmp:
                if k > K:
                    cnt += 1
                    tmp = [cuts[l][j] for l in range(h)]
                    break
        if cnt < answer:
            answer = cnt

print(answer)


import sys
readline = sys.stdin.readline

H,W,K = map(int,readline().split())
grid = [None] * (H+1)
grid[0] = [0] * (W+1)
for i in range(1,H+1):
  grid[i] = [0] + list(map(int,list(input())))
  
# 二次元累積和でチョコレートの数を管理
# 直前に選んだチョコのY座標をp,X座標をqとすると、
# チョコレートの数をO(1)で求められる
# 最初に空行を入れているので1-indexで。

for i in range(len(grid)-1):
  for j in range(len(grid[i])):
    grid[i+1][j] = grid[i][j] + grid[i+1][j]

for i in range(len(grid)):
  for j in range(len(grid[i])-1):
    grid[i][j+1] = grid[i][j] + grid[i][j+1]
  
def get_choco_cnt(i,j,p,q):
  return grid[i][j] - grid[i][q] - grid[p][j] + grid[p][q]
  
# Hが10と少ないので、切る場所9箇所をすべて試しても2^9 = 512通り
# すべてに対して、Wのどこを切るかを求める。
# 二分探索なら　O(2^(H-1) * (log W * H)) = 約51200
# 線形探索でも　O(2^(H-1) * WH) = 5,120,000

def isOk(x,lastq,cond,K,H,W):
  # xで切ったとき、iで分割されたすべての領域の数がK以下になればOK
  lastp = 0 # Hを最後に切った場所
  for j in range(H-1):
    if (cond >> j) & 1: # j+1で切る
      if get_choco_cnt(j+1,x,lastp,lastq) > K:
        return False
      lastp = j+1
  # 最後に切った場所から、最後まで
  if get_choco_cnt(H,x,lastp,lastq) > K:
    return False
  return True
  
def decide_cut(cond,lastq,K,H,W):
  ok = lastq
  ng = W+1
  while abs(ok - ng) > 1:
    mid = abs(ok + ng) // 2
    if isOk(mid,lastq,cond,K,H,W):
      ok = mid
    else:
      ng = mid
  return ok

ans = 10000
for cond in range(2 ** (H-1)):
  cut_num = (bin(cond)[2:]).count("1") # カットした回数
  lastq = 0 # 最後にカットした場所
  while lastq < W+1:
    new_lastq = decide_cut(cond,lastq,K,H,W)
    if new_lastq == W:
      break
    if new_lastq == lastq:
      cut_num = 10000
      break
    cut_num += 1
    lastq = new_lastq
  if ans > cut_num:
    ans = cut_num
print(ans)

# coding: utf-8
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)

import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=list(map(int,input().split()))
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)

tdiv=2**(h-1)
#import numpy as np
#s = np.array(s)
ans = 100100100
for i in range(tdiv):
    lis=[]
    #tmp=np.zeros(w)
    #tmp+=s[0,:]
    tmp=[s[0][ii] for ii in range(w)]
    cnt = 0
    #print(tmp)
    for j in range(h-1):
        if (i>>j&1):
            #tmp+=s[j+1,:]
            tmp=[tmp[ii]+s[j+1][ii] for ii in range(w)]
        else:
            lis.append(tmp)
            #tmp=np.zeros(w)
            #tmp+=s[j+1,:]
            tmp=[s[j+1][ii] for ii in range(w)]
            cnt+=1
    lis.append(tmp)
    #lis = np.array(lis)
    #clis=np.zeros(cnt+1)
    clis=[0 for ii in range(cnt+1)]
    #print(lis,cnt)
    tmpcnt=cnt
    for ind in range(w):
        #if any(d>k for d in lis[:,ind]):
        #if lis[:,ind].max()>k:
        if max([lis[ii][ind] for ii in range(tmpcnt+1)])>k:
            cnt=10010010
            break
        clis=[lis[ii][ind]+clis[ii] for ii in range(tmpcnt+1)]
        #if clis.max()>k:
        if max(clis)>k:
            clis=[lis[ii][ind] for ii in range(tmpcnt+1)]
            cnt+=1
    #print(cnt)
    ans = min(ans,cnt)
print(ans)
#pypyを使おう!


import numpy as np
from itertools import product
H, W, K = list(map(int, input().split()))
G = np.array([list(map(int, list(input()))) for _ in range(H)])

ans = float('inf')
for pattern in product([0, 1], repeat=H - 1):
    # スライスで横方向への割り方を表現する
    div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [10]

    # 横方向へ割った後、各ブロックについて縦方向にホワイトチョコの数を修正
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))

    # 縦方向にすでにK個より多いホワイトチョコが含まれている場合はどうにもならない
    if [r for r in rows if np.any(r > K)]:
        continue

    # 縦方向に貪欲に割っていく
    rows = [r.tolist() for r in rows]
    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    while w < W:
        for r in range(len(rows)):
            counts[r] += rows[r][w]
        if any([c > K for c in counts]):
            counts = [0] * len(rows)
            w -= 1
            tmp_ans += 1
        w += 1

    # 横に割った分を加算
    tmp_ans += len(div) - 2
    ans = min(ans, tmp_ans)

print(ans)


#na-
import itertools
H, W, K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
def check(k):
    if k <= K:
        return(True)
    else:
        return(False)
        
noans = 0
def make_lst(i):
    nonlocal noans, lst, havelst
    temp = S[0][i]
    for h in range(H-1):
        if y[h]:
            lst.append(temp)
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    lst.append(temp)
    if check(max(lst)):
        havelst = 1
    else:
        noans = 1
               
def nocut(i):
    nonlocal cutnum, lst, havelst
    prelst = []
    temp = S[0][i]
    j = 0
    for h in range(H-1):
        if y[h]:
            lst[j] += temp
            prelst.append(temp)
            j += 1
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    prelst.append(temp)
    lst[-1] += temp
    if check(max(lst)):
        return(True)
    else:
        cutnum += 1
        lst = prelst        
                 
ans = float("inf")
cutlst = []    
for y in itertools.product((0, 1), repeat=H-1):
    havelst = 0
    lst = []
    cutnum = sum(y)
    for x in range(W):
        if noans:
            break
        if havelst:
            nocut(x)
        else:
            make_lst(x)
    if noans==1:
        noans = 0
        continue
    ans = min(cutnum, ans)
print(ans)

import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, list(input()))) for _ in range(H)])
 
ans = float('inf')
for pattern in product([0, 1], repeat=H - 1):
    # スライスで横方向への割り方を表現する
    div = [0] + [i for i, p in enumerate(pattern, start=1) if p == 1] + [10]
 
    # 横方向へ割った後、各ブロックについて縦方向にホワイトチョコの数を修正
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))
 
    # 縦方向にすでにK個より多いホワイトチョコが含まれている場合はどうにもならない
    if [r for r in rows if np.any(r > K)]:
        continue
 
    # 縦方向に貪欲に割っていく
    rows = [r.tolist() for r in rows]
    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    while w < W:
        for r in range(len(rows)):
            counts[r] += rows[r][w]
        if any([c > K for c in counts]):
            counts = [0] * len(rows)
            w -= 1
            tmp_ans += 1
        w += 1
 
    # 横に割った分を加算
    tmp_ans += len(div) - 2
    ans = min(ans, tmp_ans)
 
print(ans)

import sys

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input().strip("\n")))) for _ in range(H)]
    sumS = [[0] * (W + 1) for _ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            sumS[h+1][w+1] = sumS[h+1][w] + sumS[h][w+1] - sumS[h][w] + S[h][w]
    minK = 1000000000000
    for h in range(2 ** (H - 1)):
        count = 0
        border = [0]
        k = h
        for i in range(H-1):
            if k % 2 == 1: 
                border.append(i+1)
                count += 1
            k //= 2
        border.append(H)
        bN = len(border)
        left = 0
        ng = False
        for right in range(1, W + 1):
            for i in range(bN - 1):  
                if sumS[border[i+1]][right] - sumS[border[i+1]][left] - sumS[border[i]][right] + sumS[border[i]][left] > K:
                    if right - 1 == left: ng = True
                    else: 
                        count += 1
                        left = right - 1
                    break
            if ng: break 
        else: minK = min(minK, count)
    print(minK)
    return 0

def __starting_point():
    solve()
__starting_point()


INF = 1<<60
def resolve():
    def judge(j):
        for i in range(group):
            cnt_Wchoco[i] += div_G[i][j]
            if cnt_Wchoco[i] > K:
                return False
        return True

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

    ans = INF
    for bit in range(1<<(H-1)):
        group = 0 # 分かれたブロック数
        row = [0]*H
        for i in range(H):
            # 分割ライン
            row[i] = group
            if bit>>i & 1:
                group += 1
        group += 1 # 1つ折ったら2つに分かれるのでプラス1, 折らなかったら1つ

        # 分割したブロックを列方向で見る
        div_G = [[0] * W for _ in range(group)]
        for i in range(H):
            for j in range(W):
                div_G[row[i]][j] += G[i][j]

        num = group-1
        cnt_Wchoco = [0]*group
        for j in range(W):
            if not judge(j):
                num += 1
                cnt_Wchoco = [0] * group
                if not judge(j):
                    num = INF
                    break
        ans = min(ans, num)

    print(ans)

def __starting_point():
    resolve()

__starting_point()

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: list(map(int, sys.stdin.readline().split()))
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    # if h == 1:
    #     tmp = max(0, mat[0].count("1") - 1)
    #     print(tmp // k)
    #     return

    ans = INF
    for i in range(2 ** (h - 1)):
        cut = format(i, "b").count("1")
        row = cut + 1

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                tmp_ans = INF
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


def __starting_point():
    main()

__starting_point()

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)

def __starting_point():
  main()
__starting_point()

import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, W, K = NMI()
    choco = [SI() for _ in range(H)]
    ans = 100000
    for case in range(2**(H-1)):
        groups = [[0]]
        for i in range(H-1):
            if (case >> i) & 1:
                groups[-1].append(i+1)
            else:
                groups.append([i+1])
        white = [0] * len(groups)

        is_badcase = False
        cut = len(groups) - 1
        for w in range(W):
            diff = [0] * len(groups)
            for gi, group in enumerate(groups):
                for h in group:
                    if choco[h][w] == "1":
                        white[gi] += 1
                        diff[gi] += 1

            if max(white) <= K:
                is_cont = True
                continue

            if max(diff) > K:
                is_badcase = True
                break

            cut += 1
            white = diff[:]
            continue

        if not is_badcase:
            ans = min(ans, cut)

    print(ans)



def __starting_point():
    main()
__starting_point()

from itertools import accumulate

h,w,k = map(int,input().split())
s = [list(map(int,"".join(input()))) for _ in range(h)]

min_split = 10**10

for i in range(2**(h-1)):
    li = []

    for j in range(h-1):
        if (i >> j)&1:
            li.append(j)
    li.append(h-1)
    lin = [0]*w
    total = []

    over = False

    for l in range(h):
        for m in range(w):
            lin[m] += s[l][m]
            if lin[m] > k:
                over = True
        if l in li:
            total.append(lin)
            lin = [0]*w

    if over:
        continue

    now = 0
    t = len(total)
    count = t-1

    for n in range(t):
        total[n] = [0]+list(accumulate(total[n]))
    for o in range(1,w+1):
        for p in range(t):
            if total[p][o]-total[p][now] > k:
                now = o-1
                count += 1
                break

    min_split = min(min_split,count)

print(min_split)

import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
S = np.zeros((H + 1, W + 1), dtype=int)
S[1:, 1:] = [[int(_) for _ in input()] for _ in range(H)]
cum = S.cumsum(axis=0).cumsum(axis=1)
# print(cum)

ans = 10**10
for bs in itertools.product([True, False], repeat=H - 1):
    bs = [True] + list(bs) + [True]
#     print(bs)
    idxs = []
    for i, b in enumerate(bs):
        if b:
            idxs += [i]
    cum2 = np.array([cum[i2] - cum[i1] for i1, i2 in zip(idxs, idxs[1:])])
    i = 0
    cnt = sum(bs) - 3
    while i < W:
        di = min(
            np.searchsorted(c[i + 1:] - c[i], K, side='right') for c in cum2)
        if di == 0:
            cnt = 10**10
            break
        i += di
        cnt += 1
    ans = min(ans, cnt)
print(ans)

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

choco = [list(map(int, list(input()))) for i in range(h)]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    # 上位ビットが上側。1が切る、0が切らない
    num_cut_yoko = bin(h_cut).count("1") # 立っているビットの個数
    num_cut = num_cut_yoko
    w_last_cut_pos = -1
    valid = True

    count_white = [0] * (num_cut_yoko + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        # print('idx', 2 ** (-i+h-1) )
        if h_cut & (2 ** (-i+h-1)):
            idx += 1
        # idx += h_cut & (2 ** (h-1) - i)
        temp_dict[i] = idx
    # print(temp_dict)

    iw = 0
    while iw < w:

        for ih in range(h):
            count_white[temp_dict[ih]] += choco[ih][iw]
        # print(iw, count_white)

        condition = max(count_white) > k
        if condition:
            if w_last_cut_pos < iw-1:
                # もしそこで切ってkを超えるなら、その手前で切る
                num_cut += 1
                w_last_cut_pos = iw - 1
                count_white = [0] * (num_cut_yoko + 1)
                # print('iw: ', iw, 'last: ', w_last_cut_pos)

            else:
                # 1つしか動かしてないのに、Kマスを超えてしまった場合は、この横の切り方では達成不可能なので次のh_cutに
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    # print(num_cut)

print(ans)


from itertools import product


def makelist(BIT):
    LIST, tmp = [], s[0]
    for si, bi in zip(s[1:], BIT):
        if bi == 1:
            LIST.append(tmp)
            tmp = si
        elif bi == 0:
            tmp = [t + sij for t, sij in zip(tmp, si)]
    else:
        LIST.append(tmp)
    return LIST


def solve(LIST):
    COST, cnt = 0, [li[0] for li in LIST]
    if any(num > k for num in cnt):
        return h * w
    for j in range(1, w):
        tmp = [t + li[j] for t, li in zip(cnt, LIST)]
        if any(num > k for num in tmp):
            COST += 1
            cnt = [li[j] for li in LIST]
        else:
            cnt = tmp[:]
    return COST


h, w, k = list(map(int, input().split()))
s = [[int(sij) for sij in input()] for _ in range(h)]

ans = h * w
for bit in product([0, 1], repeat=(h - 1)):
    numlist = makelist(bit)
    ans = min(ans, solve(numlist) + sum(bit))
print(ans)


from itertools import product
import numpy as np
HWK,*sss = open(0).read().splitlines()
H,W,K = map(int, HWK.split())
sss = [list(map(int, list(ss))) for ss in sss]
sss = np.cumsum(sss, axis=0)
 
if H == 1 or W == 1:
    print(0--sss[-1][-1]//K)
    return
 
ans = float('inf')
for flgs in product([False, True], repeat=H-1):
    cnt = sum(flgs)
    tsss = sss[[*flgs, True]]
    tsss = np.concatenate((tsss[:1], np.diff(tsss, axis=0)), axis=0).T
 
    tmp = 0
    succ = True
    for cur in tsss:
        new = tmp + cur
        if new.max() <= K:
            tmp = new
        else:
            cnt += 1
            if cur.max() > K:
                succ = False
                break
            else:
                tmp = cur
#     print(flgs)
#     print(cnt, ans, tsss)
    if succ:
        ans = min(ans, cnt)
 
print(ans)

import itertools


def main():
    H, W, K = list(map(int, input().split(' ')))
    S = [input() for _ in range(H)]
    ans = (H - 1) * (W - 1)
    for h_divs in itertools.product([0, 1], repeat=H-1):
        # 例：h_patterns = [0, 0, 1, 2, 2] -> チョコを1～2、2～3番目の行で分割
        h_patterns = [0] * H
        for h in range(1, H):
            h_patterns[h] = h_patterns[h - 1] + h_divs[h - 1]
        # 横方向には h_patterns[-1] 回割る
        div_cnt = h_patterns[-1]
        # 縦方向にはgreedyに割っていく
        white_cnt = [0] * (div_cnt + 1)
        valid_div = True  # 各列において、単体でホワイトチョコがK個より多いブロックがあったらFalse
        for w in range(W):
            new_white_cnt = [0] * (div_cnt + 1)
            for h in range(H):
                if S[h][w] == '1':
                    new_white_cnt[h_patterns[h]] += 1
            if max(new_white_cnt) > K:
                valid_div = False
                break
            should_div = False
            for r in range(len(white_cnt)):
                if white_cnt[r] + new_white_cnt[r] > K:
                    should_div = True
                    break
            if should_div:
                div_cnt += 1
                for r in range(len(white_cnt)):
                    white_cnt[r] = new_white_cnt[r]
            else:
                for r in range(len(white_cnt)):
                    white_cnt[r] += new_white_cnt[r]
        if valid_div:
            ans = min(ans, div_cnt)
    print(ans)


def __starting_point():
    main()
__starting_point()

import sys

def solve():
    input = sys.stdin.readline
    H, W, K = map(int, input().split())
    S = [input().strip("\n") for _ in range(H)]
    Ans = 10 ** 20
    Wcount = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            Wcount[h+1][w+1] = Wcount[h][w + 1] + Wcount[h + 1][w] - Wcount[h][w] + int(S[h][w])
        
            
    #print(Wcount)
    Ans = H * W + 1
    for i in range(2 ** (H - 1)):
        B = [0]
        d = i
        Hcount = 0
        for j in range(H - 1):
            if d % 2 == 1:
                B.append(j + 1)
                Hcount += 1
            d //= 2
        B.append(H)
        leftbound = 0
        TotalBound = Hcount
        NG = False
        for w in range(1, W+1):
            for b in range(Hcount + 1):
                if Wcount[B[b+1]][w] - Wcount[B[b+1]][leftbound] - Wcount[B[b]][w] + Wcount[B[b]][leftbound] > K:
                    if leftbound + 1 == w: 
                        NG = True
                    else:
                        TotalBound += 1
                        leftbound = w - 1
                    break
            if NG: break
        else: Ans = min(TotalBound, Ans)
        #print(i, B, TotalBound)
    print(Ans)

    return 0

def __starting_point():
    solve()
__starting_point()

H, W, K = map(int, input().split())
S = []
for _ in range(H):
  S.append(input())
hsummation = [[int(S[0][k])]for k in range(W)]
for k in range(W):
  for j in range(1, H):
    hsummation[k].append(hsummation[k][j-1] + int(S[j][k]))
#print(hsummation)
ans = float('inf')
anskouho = 0
h = 2**(H-1)
for j in range(2**(H-1)):
  h -= 1
  binh = "0"*(H-len(str(bin(h)))+1)+str(bin(h))[2:]
  hlist=[]
  for k in range(H-1):
    if binh[-k-1] == '1':
      hlist.append(k)
  hlist.append(-1)
  #print(hlist)
  anskouho = len(hlist)-1
  now = 0
  while now < W:
    counter = [0 for _ in range(len(hlist))]
    while now < W:
      for l in range(len(hlist)):
        if l == 0:
          counter[l] += hsummation[now][int(hlist[l])]
          continue
        else:
          counter[l] += - hsummation[now][hlist[l-1]] + hsummation[now][hlist[l]]
      if max(counter) > K:
        anskouho += 1
        break
      else:
        now += 1
    if anskouho > ans:
      break
  else:
    ans = min(ans, anskouho)
 
      #print(counter)
#print(anskouho)
print(ans)

#!python3

import itertools


INF = 10 ** 5

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


def solve(w, l):
    n = len(l) + 1
    ans = 0
    if n == 1:
        dp = 0
        for j in range(W):
            x = w[-1][j]
            if x > K:
                return INF
            dp += x
            if dp > K:
                ans += 1
                dp = x
    else:
        dp = [0] * n
        for j in range(W):
            x = [0] * n
            b = False
            for i in range(n):
                if i == 0:
                    x[i] = w[l[i]][j]
                elif i == n - 1:
                    x[i] = w[-1][j] - w[l[-1]][j]
                else:
                    x[i] = w[l[i]][j] - w[l[i-1]][j]
                if x[i] > K:
                    return INF
                dp[i] += x[i]
                if dp[i] > K:
                    b = True
            if b:
                dp = x
                ans += 1
    return ans


def main():
    w = [S[0]]
    for i in range(1, H):
        w.append([w[i-1][j] + S[i][j] for j in range(W)])

    ans = INF
    num_list = [i for i in range(H - 1)]
    for i in range(H):
        comb_list = itertools.combinations(num_list, i)
        for l in comb_list:
            ans = min(ans, i + solve(w, l))

    print(ans)


def __starting_point():
    main()

__starting_point()

h,w,k = list(map(int,input().split()));arr = [[int(i) for i in input()] for _ in range(h)]

from itertools import product
ans = 2000

for i in product([True,False],repeat=(h-1)):
    cut = sum(i)
    splits = [0] * (cut+1)
    splits[0] = arr[0][:]
    tmp = 0
    div = cut
    for j in range(1,h):
        if i[j-1]:
            tmp += 1
            splits[tmp] = arr[j][:]
        else:
            splits[tmp] = [splits[tmp][idx]+arr[j][idx] for idx in range(w)]
    
    check = 0
    for j in splits:
        check = max(check,max(j))
    if check > k:
        break
    count = [splits[j][0] for j in range(cut+1)]
    
    for j in range(1,w):
        addarr = [count[idx]+splits[idx][j] for idx in range(cut+1)]
        if max(addarr) > k:
            div += 1
            count = [splits[idx][j] for idx in range(cut+1)]
        else:
            count = addarr[:]
    ans = min(ans,div)
        
print(ans)

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

choco = [list(map(int, list(input()))) for i in range(h)]

choco_cumsum = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    choco_cumsum[i][0] = choco[i][0]
    for j in range(1, w):
        choco_cumsum[i][j] = choco_cumsum[i][j-1] + choco[i][j]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    # 上位ビットが上側。1が切る、0が切らない
    num_cut_init = bin(h_cut).count("1") # 立っているビットの個数
    num_cut = num_cut_init
    w_last_cut_pos = -1
    valid = True

    count_white = [0] * (num_cut_init + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        # print('idx', 2 ** (-i+h-1) )
        if h_cut & (2 ** (-i+h-1) ):
            idx += 1
        # idx += h_cut & (2 ** (h-1) - i)
        temp_dict[i] = idx
    # print(temp_dict)

    iw = 0
    while iw < w:

        for ih in range(h):
            count_white[temp_dict[ih]] += choco[ih][iw]
        # print(iw, count_white)

        condition = max(count_white) > k
        if condition:
            if w_last_cut_pos < iw-1:
                # もしそこで切ってkを超えるなら、その手前で切る
                num_cut += 1
                w_last_cut_pos = iw - 1
                count_white = [0] * (num_cut_init + 1)
                # print('iw: ', iw, 'last: ', w_last_cut_pos)

            else:
                # 1つしか動かしてないのに、Kマスを超えてしまった場合は、この横の切り方では達成不可能なので次のh_cutに
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    # print(num_cut)

print(ans)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = list(map(int, readline().split()))
    S = [list(map(int, readline().strip())) for j in range(H)]

    white = 0
    for line in S:
        white += sum(line)

    if white <= K:
        print((0))
        return

    # 横線の決め方を全探索
    ans = 10**5
    for pattern in range(2**(H-1)):
        # 初期化
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [[0]*W]*(ly + 1)
        line = 0
        for i in range(H):
            y[line] = [y[line][j] + S[i][j] for j in range(W)]
            if (pattern >> i) & 1:
                line += 1

        # 各列の値を加算していく
        count = [0]*(ly + 1) 
        for col in zip(*y):
            # Kより大きい値を加算する場合は不成立
            if any(a > K for a in col):
                impossible = True
                break
            for i, a in enumerate(col):
                count[i] += a
                # 和がKより大きければカット数を増やす
                if count[i] > K:
                    x += 1
                    count = list(col) 
                    break
            if x + ly > ans:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


def __starting_point():
    main()

__starting_point()

#!/usr/bin python3
# -*- coding: utf-8 -*-

h, w, k = map(int, input().split())
a = [list(map(int, list(input()))) for _ in range(h)]

ret = 100000
for i in range(2 ** (h-1)):
    hi = [0] * h
    for j in range(h-1):
        hi[j+1] += hi[j] + (i >> j & 1)
    cnt = max(hi)
    pj = 0
    x = []
    while pj < w:
        s = [0] * 10
        fg = False
        for j in range(pj, w):
            for t in range(h):
                s[hi[t]] += a[t][j]
            if max(s)>k:
                if j == pj:
                    cnt = 100000
                    fg = True
                    break
                else:
                    x.append(j)
                    cnt += 1
                    pj = j
                break
            if j == w-1:
                pj = w
                break
        if fg:
            break
    ret = min(ret, cnt)
print(ret)

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

ans = H+W+9999
for b in range(1<<(H-1)):
    mp = [0]
    k = 0
    for i in range(H-1):
        if b&(1<<i):
            k += 1
        mp.append(k)
    tmp = bin(b).count('1')
    ws = [0] * H
    muri = False
    for col in zip(*S):
        for i,c in enumerate(col):
            if c == '1':
                ws[mp[i]] += 1
        if any(w > K for w in ws):
            ws = [0] * len(mp)
            for i,c in enumerate(col):
                if c == '1':
                    ws[mp[i]] += 1
            if any(w > K for w in ws):
                muri = True
                break
            tmp += 1
        if muri:
            break
    if not muri:
        ans = min(ans, tmp)
print(ans)

from itertools import groupby, accumulate, product, permutations, combinations
def solve():
    H, W, K = list(map(int, input().split()))
    S = [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()))


H,W,K=list(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)




import sys
import numpy as np
from itertools import combinations_with_replacement,product
def input(): return sys.stdin.readline().rstrip()

def culc(array,k,count):
    array=array.T
    cuts=np.zeros(array.shape[1])
    for i in range(array.shape[0]):
        if any(array[i]>k):
            return 10**6
        elif any(array[i]+cuts>k):
            cuts=array[i]
            count+=1
        else:
            cuts+=array[i]
    return count


def main():
    h,w,k=map(int, input().split())
    choco=np.zeros((h,w))
    for i in range(h):
        choco[i]=list(input())
    ans=10**6
    choco=choco.astype(np.int64)
    for bit in product([0,1],repeat=h-1):
        if sum(bit)>=ans:
            break
        chocos=choco.copy()
        cut=chocos[0].reshape([1,w])
        for i in range(h-1):
            if bit[i]==1:
                cut=np.concatenate([cut,chocos[i+1].reshape([1,w])])
            else:
                cut[-1]+=chocos[i+1]
        ans=min(ans,culc(cut,k,sum(bit)))
    print(ans)


def __starting_point():
    main()
__starting_point()

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input() for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(group)
        cnt = zeros.copy()
        w = 0
        while w < W:
            now = zeros.copy()
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = zeros.copy()
                    break
                cnt[g] += now[g]
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

from operator import add

INF = 10**6

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

def check(chocoss):
    if max(list(map(max, chocoss))) > K:
        return INF

    L = len(chocoss)
    num = 0
    Bs = [0] * L
    for j in range(W):
        for i in range(L):
            if Bs[i] + chocoss[i][j] > K:
                num += 1
                Bs = [chocoss[i][j] for i in range(L)]
                break
        else:
            for i in range(L):
                Bs[i] += chocoss[i][j]

    return num

ans = INF
for ptn in range(1<<(H-1)):
    chocoss = [Ass[0]]
    num = 0
    for i in range(H-1):
        if (ptn>>i) & 1:
            chocoss.append(Ass[i+1])
            num += 1
        else:
            chocoss[-1] = list(map(add, chocoss[-1], Ass[i+1]))

    num += check(chocoss)
    if num < ans:
        ans = num

print(ans)


import numpy as np
import itertools
H, W, K = [int(_) for _ in input().split()]
S = np.zeros((H + 1, W + 1), dtype=int)
S[1:, 1:] = [[int(_) for _ in input()] for _ in range(H)]
cum = S.cumsum(axis=0).cumsum(axis=1)
#sum(a,b -> x,y) (1-indexed)
#cum[x][y]+cum[a-1][b-1]-cum[a-1][y]-cum[x][b-1]
ans = 10**10
for bs in itertools.product([True, False], repeat=H - 1):
    bs = [True] + list(bs) + [True]
    idxs = []
    for i, b in enumerate(bs):
        if b:
            idxs += [i]
    cum2 = np.array([cum[i2] - cum[i1] for i1, i2 in zip(idxs, idxs[1:])])
    i = 0
    cnt = sum(bs) - 3
    while i < W:
        di = min(
            np.searchsorted(c[i + 1:] - c[i], K, side='right') for c in cum2)
        if di == 0:
            cnt = 10**10
            break
        i += di
        cnt += 1
    ans = min(ans, cnt)
print(ans)


# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W, K = lr()
S = np.array([list(map(int, sr())) for _ in range(H)])
Scum = np.cumsum(S, axis=1)
INF = 10 ** 10
answer = INF
for pattern in range(1<<H-1):
    cnt = 0
    Tcum = Scum.copy()
    for i in range(H-1):
        if pattern>>i & 1:  # 切れ目
            cnt += 1
        else:
            Tcum[i+1] += Tcum[i]
    prev = -1
    w = 0
    Tcum = Tcum.tolist()
    while w < W:
        cut = False
        for i in range(H):
            if Tcum[i][w] - (Tcum[i][prev] if prev >= 0 else 0) > K:
                cut = True
                break
        if cut:
            if prev == w - 1:  # 1列でKをオーバー
                break
            cnt += 1
            prev = w - 1
        else:
            w += 1
    else:
        answer = min(answer, cnt)

print(answer)


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = list(map(int, readline().split()))
    S = [list(map(int, readline().strip())) for j in range(H)]

    white = 0
    for line in S:
        white += sum(line)

    if white <= K:
        print((0))
        return

    # 横線の決め方を全探索
    ans = 10**5
    for pattern in range(2**(H-1)):
        # 初期化
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [S[0]]
        line = 0
        for i in range(1,H):
            if (pattern >> i-1) & 1:
                line += 1
                y.append(S[i])
            else:
                y[line] = [y[line][j] + S[i][j] for j in range(W)]

        # 各列の値を加算していく
        count = [0]*(ly + 1) 
        for j in range(W):
            for i in range(line+1):
                if y[i][j] > K :
                    impossible = True
                    break

                count[i] += y[i][j]
                if count[i] > K:
                    x += 1
                    for i in range(line+1):
                        count[i] = y[i][j] 
                    break
            if x + ly > ans or impossible:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


def __starting_point():
    main()

__starting_point()

h,w,k=map(int,input().split())
g=[[int(c) for c in 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)

h,w,k = map(int,input().split())
s = [list(map(int,input().strip())) for i in range(h)]
from copy import deepcopy

ss = deepcopy(s)
for i in range(h):
    for j in range(w-1):
        ss[i][j+1] += ss[i][j]


def gru_hol(HOL): # セットから切り方を作る
    groups_a = []
    group_a = [0]
    for i in range(h-1):
        if(HOL[i] == 1):
            groups_a.append(group_a)
            group_a = [i+1]
        else:
            group_a.append(i+1)
    groups_a.append(group_a)
    return groups_a

def nex_hol(HOL): #次のセットを作る
    for j in range(h-1):
        if(HOL[j] == 0):
            HOL[j] = 1
            for k in range(0,j):
                HOL[k] = 0
            break
    return HOL

def cutsum(grp,lscut,nxcut): #groupのlastcut~nextcutのホワイトチョコを数える
    count = 0
    for i in grp:
        if(lscut != 0):
            count = count + ss[i][nxcut-1] - ss[i][lscut-1]
        else:
            count += ss[i][nxcut-1] 
    return count

def cutcheck(grp_a,lscut_a): #切ってもダメかチェック
    ct_a = 0
    for i in grp_a:
        ct_a += s[i][lscut_a]
    if(ct_a > k):
        return False
    else:
        return True

min_cut = h + w - 2
hol = [0]*(h-1)
for i in range(2**(h-1)):
    fl_ag = 0
    lastcut = 0
    cuts = 0 #切る回数
    groups = gru_hol(hol) #groupsを作る
    for j in range(1,w):
        flag = 0
        for group in groups:
            if(cutsum(group,lastcut,j+1) > k):
                if(cutcheck(group,lastcut) == False):
                    fl_ag = 1 #groupからやり直し
                    break
                else:
                    flag = 1
        if(fl_ag == 1):
            break
        if(flag == 1):
            cuts += 1
            lastcut = j

    if(cutcheck(group,w-1) == True):
        min_cut = min(min_cut,cuts+sum(hol))
    nex_hol(hol)

print(min_cut)

# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def solve():
    H, W, K = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = int(1e15)
    for i in range(1 << (H - 1)):
        cut = 0
        pc = 1
        whites = [[0 for _ in range(W)] for _ in range(H)]
        for j in range(H - 1):
            for w in range(W):
                whites[cut][w] += S[j][w] == '1'
            if i >> j & 1:
                cut += 1
                pc += 1
        for w in range(W):
            whites[cut][w] += S[-1][w] == '1'
        flag = True
        for line in whites:
            for cnt in line:
                if cnt > K:
                    flag = False
        if not flag:
            continue
        cnt = [0 for _ in range(pc)]
        for w in range(W):
            flag = True
            for j in range(pc):
                if cnt[j] + whites[j][w] > K:
                    flag = False
            if not flag:
                cnt = [0 for _ in range(pc)]
                cut += 1
            for j in range(pc):
                cnt[j] += whites[j][w]
        ans = min(ans, cut)
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


def __starting_point():
    main()

__starting_point()

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    H, W, K = lr()
    S = []
    for i in range(H):
        S.append([int(s) for s in sr()])
    ans = 2000
    idx = [0]*H
    for div in range(1<<(H-1)):
        g = 0
        for i in range(H):
            idx[i] = g
            if div>>i&1:
                g += 1
        g += 1
        c = [[0]*W for i in range(g)]
        for i in range(H):
            for j in range(W):
                c[idx[i]][j] += S[i][j]
        ok = True
        for i in range(g):
            for j in range(W):
                if c[i][j] > K:
                    ok = False
        if not ok:
            continue
        num = 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):
                num += 1
                now = [0]*g
                add(j)
        ans = min(ans, num)
    print(ans)
resolve()

import sys
input = sys.stdin.readline

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

bit = 2**(H-1)
ans = 1010
for bi in range(bit):
    w = 0
    cnt = bin(bi).count('1')
    counter_1 = [0]*H
    
    while w <W:
        i=0
        for h in range(H):
            if S[h][w] == '1':
                counter_1[i]+=1
                if counter_1[i]>K:
                    cnt +=1
                    counter_1 = [0]*H
                    w -=1
                    break
            if bi >>h & 1:
                i+=1
        w+=1
        if cnt>=ans:
            break
    ans = min(ans,cnt)
print(ans)


def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]
 
def split(ar, k, w):
    a = 0
    if max(max(ar)) > k:
      return -1
    tm = ar[0]
    for i in range(1, w):
        tm = add(tm, ar[i])
        if max(tm) > k:
            a += 1
            tm = ar[i]
    return a        
 
h, w, k = list(map(int, input().split()))
s = [[int(i) for i in input()] for j in range(h)]
ans = h*w
 
for i in range(2**(h-1)):
    data = []
    temp = s[0]
    sp = bin(i+2**h)[4:]
    if ans < sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp = add(temp, s[j])
        else:
            data.append(temp)
            temp = s[j]
    data.append(temp)
    ans_ = split([list(x) for x in zip(*data)], k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)


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

a = []
for i in range(h):
  s = input()
  a.append(s)

s = [[0 for i in range(w)] for i in range(h)]

ans = h+w
for grid in itertools.product([0,1], repeat=h-1):
  ary = [[0]]
  for i in range(h-1):
    if grid[i] == 1:
      ary.append([i+1])
    else:
      ary[-1].append(i+1)
  # print (grid, ary)
  wk = 0
  for i in grid:
    if i == 1:
      wk += 1
  # print (wk)
  cnt = [0] * len(ary)
  for j in range(w):
    for ii, g in enumerate(ary):
      for b in g:
        if a[b][j] == '1':
          cnt[ii] += 1
    if any(W > k for W in cnt):
      wk += 1
      cnt = [0] * len(ary)
      for ii, g in enumerate(ary):
        for jj in g:
          if a[jj][j] == '1':
            cnt[ii] += 1
      if any(W > k for W in cnt):
        wk = h+w
        break
  ans = min(ans, wk)
print (ans)

import itertools

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

# process
ans = H*W

for divr in range(1<<(H-1)):    # 横方向の分割を総当たり
    row = 0
    Sr = [[S[0][i] for i in range(W)]]
    for i in range(1, H):
        if 1&(divr>>i-1):
            row += 1
            Sr.append([S[i][j] for j in range(W)])
        else:
            Sr[row] = [Sr[row][j]+S[i][j] for j in range(W)]

    # 縦方向の分割を加算
    cnt = [0]*(row+1)
    ans_ = row
    flg = True
    for i in range(W):
        for j in range(row+1):
            if Sr[j][i] > K:
                flg = False
                break
            cnt[j] += Sr[j][i]
            if cnt[j] > K:
                ans_ += 1
                cnt = [0]*(row+1)
                for l in range(row+1):
                    cnt[l] += Sr[l][i]
                break

        if ans_ >= ans or not flg:
            break

    if flg:
        ans = min(ans, ans_)

# output
print(ans)


import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: list(map(int, sys.stdin.readline().split()))
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    h, w, k = ns()
    mat = [list(input()) for _ in range(h)]

    if h == 1:
        tmp = max(0, mat[0].count("1") - 1)
        print((tmp // k))
        return

    ans = INF
    for i in range(2 ** (h - 1)):
        cut = format(i, "b").count("1")
        row = cut + 1

        cnt = [0 for _ in range(row)]

        idx_dic = dict()
        tmp_idx = 0
        for j in range(h):
            idx_dic[j] = tmp_idx
            if i >> j & 1:
                tmp_idx += 1

        tmp_ans = cut
        xi = 0
        brkflg = True
        while xi < w:
            yi = 0
            prev_brkflg = brkflg
            brkflg = False
            while yi < h:
                if mat[yi][xi] == "1":
                    cnt[idx_dic[yi]] += 1
                    if cnt[idx_dic[yi]] > k:
                        cnt = [0 for _ in range(row)]
                        xi -= 1
                        brkflg = True
                        tmp_ans += 1
                        break

                yi += 1
            if brkflg and prev_brkflg:
                tmp_ans = INF
                break
            xi += 1
        ans = min(ans, tmp_ans)

    print(ans)


def __starting_point():
    main()

__starting_point()

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = map(int, readline().split())
    S = [list(map(int, readline().strip())) for j in range(H)]
    
    white = 0
    for line in S:
        white += sum(line)
 
    if white <= K:
        print(0)
        return
 
    # 横線の決め方を全探索
    ans = 10**5
    
    #yに横線Patternごとの列合計を作成
    #入力例１のPattern[bin(2)]場合、y=[[1,1,1,0,0], [1,0,1,1,2]]
    for pattern in range(2**(H-1)):
        # 初期化
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [S[0]]
        line = 0
        for i in range(1,H):
            if (pattern >> i-1) & 1:
                line += 1
                y.append(S[i])
            else:
                y[line] = [y[line][j] + S[i][j] for j in range(W)]
 
        # 各列の値を加算していく
        count = [0]*(ly + 1) 
        for j in range(W):
            for i in range(line+1):
                if y[i][j] > K :
                    impossible = True
                    break
 
                count[i] += y[i][j]
                #print("横Pattern{} 縦列まで　{} カウント数{} 縦線の数{}".format(i, j, count[i], x))
                #横Patten毎にｊ列までのホワイトチョコ合計数をカウント、
                #カウント＞Kとなったら、縦線数を＋１、その列値でカウント数を初期化
                if count[i] > K:
                    x += 1
                    for i in range(line+1):
                        count[i] = y[i][j]
                    break
            #x縦線の数 + ly横線の数がAnsより大きくなったらBreak
            if x + ly > ans or impossible:
                impossible = True
                break
        if impossible:
            x = 10**6
        #x縦線の数 + ly横線の数がAnsより小さくなったらAnsを更新
        ans = min(ans, x + ly)
 
    print(ans)
 
 
main()

def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input()[:-1] for _ in range(H) ]
    
    loop_H = range(H)
    loop_W = range(W)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # 縦に切っていく
        cut = group_number
        zeros = [0] * len(group)
        cnt = zeros.copy()
        w = 0
        while w < W:
            now = zeros.copy()
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = zeros.copy()
                    break
                cnt[g] += now[g]
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()

# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = list(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)


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

choco = [[0] * w for _ in range(h)]

for i in range(h):
    s = input()
    for j in range(w):
        choco[i][j] = int(s[j])

ans = float("inf")
for bit in range(1 << (h - 1)):
    idx = [0] * h
    group = 0
    for i in range(h):
        idx[i] = group
        if (bit >> i) & 1:
            group += 1
    group += 1
    array = [[0] * w for _ in range(group)]
    for j in range(w):
        for i in range(h):
            array[idx[i]][j] += choco[i][j]

    cnt = group - 1
    cum = [0] * group
    canAdd = True
    for i in range(w):
        for j in range(group):
            if cum[j] > k:
                canAdd = False

        if ans <= cnt:
            canAdd = False

        if canAdd is False:
            break

        for j in range(group):
            tmp = cum[j] + array[j][i]
            if tmp > k:
                cnt += 1
                for l in range(group):
                    cum[l] = array[l][i]
                break
            cum[j] += array[j][i]

    if canAdd:
        ans = min(ans, cnt)

print(ans)


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)

def __starting_point():
  main()
__starting_point()

def column_check(grp, grp_count, choco, h, j, k):
    """ 0:成功（更新も反映）  1:失敗（区切った結果を返す） 2:不可能 """
    # この行のグループ毎のカウント
    curr_count = [0] * len(grp_count)
    # 数える
    for i in range(h):
        if choco[i][j] == '0':
            continue
        curr_count[grp[i]] += 1
    # この行だけでk越えてたら現在の横の切り方では不可能
    for cc in curr_count:
        if cc > k:
            return 2
    # ここまでの行と合わせてkを越えないかチェック
    for i, cc in enumerate(curr_count):
        grp_count[i] += cc
        # 越えてたら、grp_countを現在の行に上書き
        if grp_count[i] > k:
            grp_count[:] = curr_count
            return 1
    return 0


def solve(h, w, k, choco):
    ans = 10 ** 9
    grp = [0] * h
    for bit in range(1 << (h - 1)):
        g = 0
        for i in range(h):
            grp[i] = g
            if (bit >> i) & 1:
                g += 1

        grp_count = [0] * (g + 1)
        tmp = 0
        possible = True
        for j in range(w):
            result = column_check(grp, grp_count, choco, h, j, k)
            if result == 2:
                possible = False
                break
            if result == 1:
                tmp += 1

        if not possible:
            continue

        ans = min(ans, tmp + bin(bit).count('1'))

    return ans


h, w, k = list(map(int, input().split()))
choco = [input() for _ in range(h)]
print((solve(h, w, k, choco)))


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

choco = [list(map(int, list(input()) )) for i in range(h)]

ans = h + w + 1

for h_cut in range(2**(h-1)):
    # 上位ビットが上側。1が切る、0が切らない
    num_cut_yoko = bin(h_cut).count("1") # 立っているビットの個数
    num_cut = num_cut_yoko
    w_last_cut_pos = -1
    valid = True

    count_white = [0] * (num_cut_yoko + 1)
    temp_dict = {}
    idx = 0
    temp_dict[0] = idx
    for i in range(1, h):
        # print('idx', 2 ** (-i+h-1) )
        if h_cut & (2 ** (-i+h-1) ):
            idx += 1
        # idx += h_cut & (2 ** (h-1) - i)
        temp_dict[i] = idx
    # print(temp_dict)

    iw = 0
    while iw < w:

        for ih in range(h):
            count_white[temp_dict[ih]] += choco[ih][iw]
        # print(iw, count_white)

        condition = max(count_white) > k
        if condition:
            if w_last_cut_pos < iw-1:
                # もしそこで切ってkを超えるなら、その手前で切る
                num_cut += 1
                w_last_cut_pos = iw - 1
                count_white = [0] * (num_cut_yoko + 1)
                # print('iw: ', iw, 'last: ', w_last_cut_pos)

            else:
                # 1つしか動かしてないのにk個を超えた場合は、この横方向の切り方で達成不可能なので、次のh_cutに進む
                # このとき切断回数の最小値の更新をしないように注意!
                valid = False
                break
        
        else:
            iw += 1
    
    if valid:
        ans = min(ans, num_cut)
    # print(num_cut)

print(ans)


H,W,K=list(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()



import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = list(map(int, readline().split()))
    S = [list(map(int, readline().strip())) for j in range(H)]

    white = 0
    for line in S:
        white += sum(line)

    if white <= K:
        print((0))
        return

    # 横線の決め方を全探索
    ans = 10**5
    for pattern in range(2**(H-1)):
        # 初期化
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [[0]*W]*(ly + 1)
        line = 0
        for i in range(H):
            y[line] = [y[line][j] + S[i][j] for j in range(W)]
            if (pattern >> i) & 1:
                line += 1

        # 各列の値を加算していく
        count = [0]*(ly + 1) 
        for j in range(W):
            for i in range(line+1):
                if y[i][j] > K :
                    impossible = True
                    break

                count[i] += y[i][j]
                if count[i] > K:
                    x += 1
                    for i in range(line+1):
                        count[i] = y[i][j] 
                    break
            if x + ly > ans or impossible:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


def __starting_point():
    main()

__starting_point()

# E - Dividing Chocolate
import numpy as np

H, W, K = list(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)




# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(H, W, K, Si):
    Si = [[int(i) for i in S] for S in Si]
    ans = H + W
    for i in range(2 ** (H - 1)):
        h_border = bin(i).count('1')
        w_border = 0
        white_counts = [0] * (h_border + 1)
        choco_w = 0
        for w in range(W):
            choco_w += 1
            wc_num = 0
            tmp_count = [0] * (h_border + 1)
            for h in range(H):
                white_counts[wc_num] += Si[h][w]
                tmp_count[wc_num] += Si[h][w]
                if i >> h & 1:
                    wc_num += 1
            if max(white_counts) > K:
                if choco_w == 1:
                    break  # 1列の時点で > K の場合は条件を達成できない
                w_border += 1
                white_counts = tmp_count
                choco_w = 1
        else:
            ans = min(ans, h_border + w_border)
    print(ans)


def __starting_point():
    H, W, K = list(map(int, input().split()))
    Si = [input() for _ in range(H)]
    solve(H, W, K, Si)

    # # test
    # from random import randint
    # from func import random_str
    # 
    # H, W, K = 10, 1000, randint(1, 100)
    # Si = [random_str(W, '01') for _ in range(H)]
    # print(H, W, K)
    # for S in Si:
    #     print(S)
    # solve(H, W, K, Si)

__starting_point()

h,w,k = list(map(int,input().split())); arr = [[int(i) for i in input()] for _ in range(h)]

from itertools import product
ans = 2000

for cond in product([True,False],repeat=(h-1)):
    cut = sum(cond); div = 0
    splits = [0] * (cut+1); splits[0] = arr[0][:]
    for i in range(1,h):
        if cond[i-1]:
            div += 1
            splits[div] = arr[i][:]
        else:
            splits[div] = [splits[div][j]+arr[i][j] for j in range(w)]
    
    check = [max(i) for i in splits]
    if max(check) > k:
        break
    count = [i[0] for i in splits]
    
    for j in range(1,w):
        addarr = [count[i]+splits[i][j] for i in range(cut+1)]
        if max(addarr) > k:
            div += 1
            count = [splits[i][j] for i in range(cut+1)]
        else:
            count = addarr[:]
    ans = min(ans,div)
        
print(ans)

import sys
import itertools
import pprint
input = lambda: sys.stdin.readline().rstrip()

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

Stsum = [[0 for _ in range(W + 1)] for _ in range(H + 1)]
for i in range(H):
    for j in range(W):
        Stsum[i + 1][j + 1] = Stsum[i + 1][j] + S[i][j]
for j in range(W):
    for i in range(H):
        Stsum[i + 1][j + 1] += Stsum[i][j + 1]


def count_white(l, r, u, b):
    return Stsum[b][r] - Stsum[u][r] - Stsum[b][l] + Stsum[u][l]


def solve():

    comb = list(itertools.product(list(range(2)), repeat=H - 1))

    ans = 10 ** 9 + 7
    for c in comb:

        hc = [0] + [i + 1 for i, x in enumerate(c) if x == 1] + [H]
        l, w = 0, 1
        cut_count = 0
        search = False
        p_cut = True

        while w <= W:
            cut = True
            for h in range(0, len(hc) - 1):
                if count_white(l, w, hc[h], hc[h + 1]) > K:
                    cut = False
                    break
            else:
                search = True

            if not cut:
                if search:
                    l = w - 1
                    cut_count += 1
                    search = False
                else:
                    p_cut = False
                    break
            else:
                w += 1

        if p_cut:
            ans = min(ans, cut_count + len(hc) - 2)

    print(ans)


def __starting_point():
    solve()

__starting_point()

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    h, w, k = map(int, input().split())
    field = [[] for i in range(h)]
    for i in range(h):
        field[i] = [int(s) for s in input()]
    import numpy as np
    field = np.array(field, dtype=int)
    inf = 10 **4
    ans = inf
    for i in range(2**(h-1)):
        prev = 0
        damy = []
        tmp_ans = format(i, 'b').count('1')
        for j in range(h-1):
            if (i >> j)&1:
                damy.append(field[prev:j+1].sum(axis=0))
                prev = j+1
        damy.append(field[prev:].sum(axis=0))
        damy = np.array(damy,dtype=int).T
        if (damy > k).any():
            continue

        prev = 0
        cnt_w = np.zeros(tmp_ans+1, dtype=int)
        for l in range(w):
            cnt_w += damy[l]
            if (cnt_w > k).any():
                cnt_w = damy[l]
                tmp_ans += 1
            
        ans = min(ans, tmp_ans)
    print(ans)


def __starting_point():
    main()
__starting_point()

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    H,W,K = list(map(int, readline().split()))
    S = [readline().strip() for j in range(H)]

    white = []
    for line in S:
        white.append(line.count("1"))
    white_total = sum(white)

    if white_total <= K:
        print((0))
        return

    # 横線の決め方を全探索
    ans = 10**5
    for pattern in range(2**(H-1)):
        # 初期化
        impossible = False
        x = 0
        ly = bin(pattern).count("1")
        y = [[0]*W]*(ly + 1)
        line = 0
        for i in range(H):
            y[line] = [y[line][j] + int(S[i][j]) for j in range(W)]
            if (pattern >> i) & 1:
                line += 1

        # 各列の値を加算していく
        count = [0]*(ly + 1) 
        for col in zip(*y):
            # Kより大きい値を加算する場合は不成立
            if any(a > K for a in col):
                impossible = True
                break
            for i, a in enumerate(col):
                count[i] += a
                # 和がKより大きければカット数を増やす
                if count[i] > K:
                    x += 1
                    count = list(col) 
                    break
            if x + ly > ans:
                impossible = True
                break
        if impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


def __starting_point():
    main()

__starting_point()

import sys

#da[i][j]:(0,0)~(i,j)の長方形の和
def da_generate(h, w, a):
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da

#da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(p, q, x, y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y] - da[x][q - 1]
    if q == 0:
        return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1] + da[p - 1][q - 1]

H, W, K = map(int, sys.stdin.readline().rstrip().split())
grid = [list(map(int, list(sys.stdin.readline().rstrip()))) for _ in range(H)]
da = da_generate(H, W, grid)

ans = 10 ** 18
for i in range(2**(H - 1)):
    res = 0
    s = [k for k, j in enumerate(range(H), 1) if i >> j & 1] # s行は含まない
    res += len(s)
    s.append(H)
    y = 0
    for w in range(1, W + 1): # w行は含まない
        x = 0
        flag = False
        for s_i in s:
            if da_calc(x, y, s_i - 1, w - 1) > K:
                if y + 1 < w:
                    res += 1
                    y = w - 1
                else:
                    flag = True
                break
            x = s_i
        else:
            pass
        if flag:
            break
    else:
        ans = min(ans, res)

print(ans)

h,w,k = list(map(int,input().split())); arr = [[int(i) for i in input()] for _ in range(h)]

from itertools import product
ans = 2000

for cond in product([True,False],repeat=(h-1)):
    cut = sum(cond)
    splits = [arr[0][:]]
    for i in range(1,h):
        if cond[i-1]:
            splits.append(arr[i][:])
        else:
            splits[-1] = [splits[-1][j]+arr[i][j] for j in range(w)]
    
    check = [max(i) for i in splits]
    if max(check) > k:
        break
    count = [i[0] for i in splits]
    
    div = cut
    for j in range(1,w):
        addarr = [count[i]+splits[i][j] for i in range(cut+1)]
        if max(addarr) > k:
            div += 1
            count = [splits[i][j] for i in range(cut+1)]
        else:
            count = addarr[:]
    ans = min(ans,div)
        
print(ans)

# https://atcoder.jp/contests/abc159/submissions/11108540

def main():
    def calc(group):
        ret = max(group)
        ctr = [0] * H
        for c in range(W):
            need_cut = False
            for r, g in enumerate(group):
                ctr[g] += s[r][c]
                if ctr[g] > K:
                    need_cut = True
                    break

            if need_cut:
                ctr = [0] * H
                ret += 1
                for r, g in enumerate(group):
                    ctr[g] += s[r][c]
                    if ctr[g] > K:
                        return H * W
                continue
        return ret

    def gen():
        from itertools import accumulate, product

        for prod in product(list(range(2)), repeat=H - 1):
            group = [0]
            group.extend(accumulate(prod))
            yield calc(group)

    H, W, K = list(map(int, input().split()))
    s = []
    for _ in range(H):
        *row, = list(map(int, input()))
        s.append(row)

    ret = min(gen())
    print(ret)


def __starting_point():
    main()

__starting_point()

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    h,w,k = LI()
    aa = [[int(c) for c in S()] for _ in range(h)]

    def f(hs):
        l = len(hs)
        c = [0] * l
        r = l - 1
        for i in range(w):
            nc = [0] * l
            bf = False
            for j in range(l):
                for h in hs[j]:
                    nc[j] += aa[h][i]
                if nc[j] > k:
                    return -1
                if nc[j] + c[j] > k:
                    bf = True
            if bf:
                r += 1
                c = nc
            else:
                for j in range(l):
                    c[j] += nc[j]
        return r

    r = inf
    for bi in range(2**(h-1)):
        hs = [[0]]
        for i in range(h-1):
            if 2**i & bi > 0:
                hs.append([])
            hs[-1].append(i+1)
        t = f(hs)
        if t >= 0 and r > t:
            r = t

    return r


print(main())





"""
References: <https://www.hamayanhamayan.com/entry/2020/03/22/231629>
"""
import sys
from itertools import product

input = sys.stdin.readline


def main():
    H, W, K = list(map(int, input().split()))
    S = [None] * H
    for i in range(H):
        S[i] = input().rstrip()

    ans = float("inf")
    for comb in product(list(range(2)), repeat=(H - 1)):
        n_cut = sum(comb)
        if n_cut >= ans:
            continue

        group = []
        g_id = 0
        for c in comb:
            group.append(g_id)
            if c == 1:
                g_id += 1
        group.append(g_id)

        w = 0
        while w < W:
            count = [0] * (g_id + 1)
            next_w = w
            for x in range(w, W):
                over_K = False
                for y in range(H):
                    if S[y][x] == "1":
                        count[group[y]] += 1
                        if count[group[y]] > K:
                            over_K = True
                            break
                if over_K:
                    break
                next_w += 1

            # Impossible: over K in one column
            if next_w == w:
                n_cut = float("inf")
                break
            w = next_w

            if over_K:
                n_cut += 1
            if n_cut >= ans:
                break

        if n_cut < ans:
            ans = n_cut

    print(ans)


def __starting_point():
    main()

__starting_point()

# E - Dividing Chocolate
import numpy as np

H, W, K = list(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)




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

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

ans = 10**10
for i in range(2**(H-1)):   # iはbit
    rel = [0 for h in range(H)]
    a,b = 0,0
    for h in range(H-1):
        if i>>h&1:
            b += 1
        rel[h+1] = b

    a += b

    cnt = [0 for j in range(b+1)]
    for w in range(W):
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1
        
        OK = True
        for j in range(b+1):
            if cnt[j] > K:
                OK = False
                break
        
        if OK:
            continue

        a += 1
        cnt = [0 for j in range(b+1)]
        for h in range(H):
            if S[h][w] == '1':
                cnt[rel[h]] += 1

        OK2 = True
        for j in range(b+1):
            if cnt[j] > K:
                OK2 = False
                break
        
        if OK2:
            continue
        a = 10**10
        break
    ans = min(ans,a)
print(ans)


import sys
input = sys.stdin.readline

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

bit = 2**(H-1)
ans = (H-1)+(W-1)
for bi in range(bit):
    w = 0
    cnt = bin(bi).count('1')
    counter_1 = [0]*H
    
    while w <W:
        i=0
        for h in range(H):
            if S[h][w] == '1':
                counter_1[i]+=1
                if counter_1[i]>K:
                    cnt +=1
                    counter_1 = [0]*H
                    w -=1
                    break
            if bi >>h & 1:
                i+=1
        w+=1
        if cnt>=ans:
            break
    ans = min(ans,cnt)
print(ans)


# https://atcoder.jp/contests/abc159/tasks/abc159_e
import sys

ans = sys.maxsize
H, W, K = list(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)





def solve(choco, cut_pos, k):
    cuts = len(cut_pos) - 2
    blocks = [0] * (len(cut_pos) - 1)

    for col in zip(*choco):
        need_cut = False
        for i, blk in enumerate(zip(cut_pos, cut_pos[1:])):
            s, e = blk
            white = sum(col[s:e])
    
            if white > k:
                return float('inf')

            if blocks[i] + white > k:
                need_cut = True
                break
            else:
                blocks[i] += white

        if need_cut:
            for i, blk in enumerate(zip(cut_pos, cut_pos[1:])):
                s, e = blk
                blocks[i] = sum(col[s:e])

        cuts += need_cut
    # print('cuts:', cuts)
    return cuts


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

    choco = [[int(s) for s in list(input())] for _ in range(h)]
    min_cuts = float('inf')

    for cuts in range(1 << (h-1)):
        cut_pos = [0] + [i+1 for i in range(h-1) if cuts & (1 << i)] + [h]
        min_cuts = min(min_cuts, solve(choco, cut_pos, k))

    print(min_cuts)


def __starting_point():
    main()

__starting_point()

import itertools
H, W, K = map(int,input().split())
S = [list(map(int,list(input()))) for _ in range(H)]
def check(k):
    if k <= K:
        return(True)
    else:
        return(False)
        
noans = 0
def make_lst(i):
    nonlocal noans, lst, havelst
    temp = S[0][i]
    for h in range(H-1):
        if y[h]:
            lst.append(temp)
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
    lst.append(temp)
    if check(max(lst)):
        havelst = 1
    else:
        noans = 1
#    print(y,i,lst, "makelst")
               
def nocut(i):
    nonlocal cutnum, lst, havelst, noans
    prelst = []
    temp = S[0][i]
    if i == W-1:
        if not check(temp):
            noans = 1
    j = 0
    for h in range(H-1):            
        if y[h]:
            lst[j] += temp
            prelst.append(temp)
            j += 1
            temp = S[h+1][i]
        else:
            temp += S[h+1][i]
        if i == W-1:
            if not check(temp):
                noans = 1
    prelst.append(temp)
    lst[-1] += temp
    if check(max(lst)):
#        print(y,i,lst,"nocut", "cutnum = ",cutnum)
        return(True)
    else:
        cutnum += 1
        lst = prelst        
#        print(y,i,lst,"cut","cutnum =",cutnum)
        
                 
ans = float("inf")    
for y in itertools.product((0, 1), repeat=H-1):
    havelst = 0
    lst = []
    cutnum = sum(y)
    for x in range(W):
        if noans:
            break
        if havelst:
            nocut(x)
        else:
            make_lst(x)
#    print(y,cutnum)
    if noans:
        noans = 0
        continue
    else:
        ans = min(cutnum, ans)
print(ans)

import numpy as np

def main():
    H, W, K = list(map(int, input().split()))
    S = []
    for _ in range(H):
        S.append(list(map(int, list(input()))))
    S = np.array(S)
    if S.sum() <= K:
        print((0))
        return
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(W, S, K, horizons, current_answer):
    answer = sum(horizons)
    # ex.
    # S  = [[1, 1, 1, 0, 0],
    #       [1, 0, 0, 0, 1],
    #       [0, 0, 1, 1, 1]]
    # horizons = [0, 1]のとき,
    # S2 = [[2, 1, 1, 0, 0],
    #       [0, 0, 1, 1, 1]]
    # となる
    top = 0
    bottom = 0
    S2 = []
    for h in horizons:
        if h == 1:
            S2.append(S[:][top:(bottom + 1)].sum(axis=0).tolist())
            top = bottom + 1
        bottom += 1
    S2.append(S[:][top:].sum(axis=0).tolist())
    # ブロック毎の累積和を計算する
    h = len(S2)
    partial_sums = [0] * h
    for right in range(W):
        current = [0] * h
        for idx in range(h):
            current[idx] = S2[idx][right]
            partial_sums[idx] += S2[idx][right]
        # 1列に含むホワイトチョコの数がkより多い場合
        if max(current) > K:
            return float('INF')
        # 無理な(ブロックの中のホワイトチョコの数をk以下にできない)場合
        if max(partial_sums) > K:
            answer += 1
            if answer >= current_answer:
                return float('INF')
            partial_sums = current
    return answer

def __starting_point():
    main()

__starting_point()

f=range
h,w,k=map(int,input().split())
g=[[int(i) for i in 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=[]
  for d in f(h):
    if i>>d&1: e+=[(u,d+1)]; c+=1; u=d+1
  e+=[(u,h)]
  for r in f(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
  else: a=min(a,c)
print(a)

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

def search(topx, topy, botx, boty, grid):
    ret = grid[boty][botx]
    if topx > 0: ret -= grid[boty][topx - 1]
    if topy > 0: ret -= grid[topy - 1][botx]
    if topx > 0 and topy > 0: ret += grid[topy - 1][topx - 1]
    return ret

def Main():
    H, W, K = read_ints()
    chocolate = [list(read_str()) for _ in range(H)]
    
    grid = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if chocolate[h][w] == '1': grid[h][w] += 1
            if w > 0: grid[h][w] += grid[h][w - 1]
            if h > 0: grid[h][w] += grid[h - 1][w]
            if h > 0 and w > 0: grid[h][w] -= grid[h - 1][w - 1]

    ans = INF
    for bit in range(1 << ~-H):
        cnt = 0
        cut = []
        for h in range(~-H):
            if bit >> h & 1:
                cnt += 1
                cut.append(h)
        cut.append(~-H)

        white = [0] * len(cut)
        topx = 0
        flag = False
        for w in range(~-W):
            topy = 0
            for i in range(len(cut)):
                if search(topx, topy, w, cut[i], grid) > K:
                    flag = True
                    break
                white[i] = search(topx, topy, w+1, cut[i], grid)
                topy = cut[i] + 1
            if flag: break
            for x in white:
                if x <= K:
                    continue
                topx = w + 1
                cnt += 1
                break
        if not flag:
            ans = min(ans, cnt)
    print(ans)
    

def __starting_point():
    Main()
__starting_point()

sel='E'
#A
if sel=='A':
    N,M=list(map(int,input().split()))
    ans=0
    ans+=M*(M-1)//2
    ans+=N*(N-1)//2
    print(ans)

#B
if sel=='B':
    def ispal(s):
        for i in range(len(s)//2+1):
            if s[i]!=s[-(i+1)]:
                return False
        return True

    S=input()
    N=len(S)
    if ispal(S) and ispal(S[:(N-1)//2]) and ispal(S[(N+3)//2-1:]):
        print('Yes')
    else:
        print('No')

#C
if sel=='C':
    L=int(input())
    print(((L**3)/27))

#D
if sel=='D':    
    N=int(input())
    A=[int(i) for i in input().split()]
    kin=list(set(A))
    cnt={}
    for k in kin:
        cnt[k]=0
    for a in A:
        cnt[a]+=1
    SUM=0
    for k in kin:
        SUM+=cnt[k]*(cnt[k]-1)//2
    for a in A:
        if cnt[a]>=2:
            print((SUM-cnt[a]+1))
        else:
            print(SUM)
        
#E
if sel=='E':
    def add(in1, in2):
        return [a + b for a, b in zip(in1, in2)]

    def split(ar, k, w):
        a = 0
        if max(max(ar)) > k:
            return -1
        tm = ar[0]
        for i in range(1, w):
            tm = add(tm, ar[i])
            if max(tm) > k:
                a += 1
                tm = ar[i]
        return a        

    h, w, k = list(map(int, input().split()))
    s = [[int(i) for i in input()] for j in range(h)]
    ans = h*w

    for i in range(2**(h-1)):
        data = []
        temp = s[0]
        sp = bin(i+2**h)[4:]
        for j in range(1, h):
            if sp[j-1] == "0":
                temp = add(temp, s[j])
            else:
                data.append(temp)
                temp = s[j]
        data.append(temp)
        ans_ = split([list(x) for x in zip(*data)], k, w)
        if ans_ == -1:
            continue
        ans_ += sp.count("1")
        if ans > ans_:
            ans = ans_
    print(ans)



# #F
# if sel=='F':
#     N,S=map(int,input().split())
#     A=[int(i) for i in input().split()]
    



import sys
input = sys.stdin.readline

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

bit = 2**(H-1)#bit全探索　横方向の割方をすべて見る
ans = (H-1)+(W-1)#ここミスるとTLE float('inf')はダメ。10**5もダメ。
for bi in range(bit):
    w = 0
    cnt = bin(bi).count('1')#横割の数
    white = [0]*H#縦割りの数を貪欲に求める
    
    while w <W:
        i=0
        for h in range(H):
            if S[h][w] == '1':
                white[i]+=1
                if white[i]>K:#超えたら割数を足す。カウンタを初期化、超えた列をもう一度足す
                    cnt +=1
                    white = [0]*H
                    w -=1
                    break
            if bi >>h & 1:
                i+=1
        w+=1
        if cnt>=ans:#すでにansを超えてたらやめる。これがないとTLE
            break
    ans = min(ans,cnt)#小さければ更新
print(ans)


import numpy as np
import itertools

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

arr = np.array(choco)

# W方向にGREEDY
count = (H-1) + (W-1)


for k in range(H):
    
    # この時点で同じ回数以上切ることが確定なら終了
    if count <= k:
        break

    # H 方向に切り込み
    for comb in itertools.combinations(range(1,H),k):

        # スライスを作っておく
        t = (None,) + comb + (None,)
        s = [slice(t[j],t[j+1],) for j in range(len(t)-1)]
        
        sum_p = [0] * (k+1)
        
        cut = k
        
        for col in zip(*choco):

            # 各ブロック毎の合計を算出
            sum_a = [sum(col[b]) for b in s]
            
            # K を超えるブロックが存在していないか？
            if any(map(K.__lt__, sum_a)):
                # 不成立
                break
            
            # 前まで分割されていないブロックと合わせて、合計を算出
            
            sum_b = [x + y for x,y in zip(sum_p, sum_a)]

            if any(map(K.__lt__, sum_b)):
                cut += 1
                sum_p = sum_a
            else:
                sum_p = sum_b
                
                # 割った位置を記録
        
        else:
            count = min(count,cut)

print(count)

from itertools import accumulate


def solve(h, w, lim, choco):
    acc = [[0] + list(accumulate(int(c == '1') for c in s)) for s in choco]
    acc = list(zip(*acc))
    acc = [[0] + list(accumulate(s)) for s in acc]
    acc = list(zip(*acc))
    # print(*acc, sep='\n')

    ans = 10 ** 9
    # i:j  h方向の分割
    # k:l  w方向の分割
    for bit in range(1 << (h - 1)):
        k = 1
        tmp = 0
        while k < w:
            # print(bin(bit), k)
            i = 0
            l = w + 1
            sp = bit | 1 << (h - 1)
            while sp:
                b = sp & -sp
                sp ^= b
                j = b.bit_length()
                lt = k
                while lt <= w and acc[j][lt] - acc[j][k - 1] - acc[i][lt] + acc[i][k - 1] <= lim:
                    lt += 1
                if lt == k:
                    break
                l = min(l, lt)
                # print('i,j,k,l', i, j, k, l, lt)
                i = j
            else:
                k = l
                if k <= w:
                    tmp += 1
                continue
            break
        else:
            # print(tmp, bin(bit).count('1'))
            ans = min(ans, tmp + bin(bit).count('1'))
    return ans


h, w, k = list(map(int, input().split()))
choco = [input() for _ in range(h)]
print((solve(h, w, k, choco)))


from itertools import product
import numpy as np
H, W, K = map(int, input().split())

grid = [[] for _ in range(H) ]
for i in range(H):
  grid[i] = list(map(int, input()))

#print(grid)

def init_cnt():
  _grid = [[0] * W for _ in range(H) ]
  _grid[0][0] = grid[0][0]
  for w in range(1, W):
    _grid[0][w] = _grid[0][w-1] + grid[0][w]
  for h in range(1, H):
    cnt_w = 0
    for w in range(W):
      cnt_w += grid[h][w]
      _grid[h][w] = _grid[h-1][w] + cnt_w
  
  return _grid

_grid = init_cnt()
#print(_grid)

# (x1, y1) ~ (x2, y2)の合計
def cnt(x1, x2, y1, y2):
  if x1 == 0 and y1 == 0:
    return _grid[x2][y2]
  if x1 == 0:
    return _grid[x2][y2] - _grid[x2][y1 -1]
  if y1 == 0:
    return _grid[x2][y2]- _grid[x1 - 1][y2]
  return _grid[x2][y2] - _grid[x2][y1 - 1] - _grid[x1 - 1][y2] + _grid[x1 - 1][y1 - 1]


ans = 1010
for i in range(2 ** (H - 1)):
  res = 0
  lst = list(k for k, j in enumerate(range(H), 1) if i >> j & 1)
  res += len(lst)
  lst.append(H)
 
  #print(lst)
  y =  0
  for w in range(1, W+1):
    x = 0
    flag = False
    
    for lst_i in lst:
      if cnt(x, lst_i - 1 ,y ,w - 1) > K:
        if y + 1 < w:
          res += 1
          y = w - 1
        else:
          flag = True
        break
        
      x = lst_i 
    else:
      pass
    if flag:
      break
  else:
    ans = min(ans, res)
    
print(ans)

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

ans=1e4 # 10000(10**4)
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)


from itertools import product

H, W, K = map(int, input().split())
l = [[0]*W for _ in range(H)]
for i in range(H):
    for j, s in enumerate(input()):
        if s=="1":
            l[i][j] = 1

dp = [[0]*(W+1) for _ in range(H+1)]
for i in range(1, H+1):
    for j in range(1, W+1):
        dp[i][j] = l[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]

f=lambda lx,ly,rx,ry:dp[ry][rx]-dp[ly-1][rx]-dp[ry][lx-1]+dp[ly-1][lx-1]

ans = H*W
for i in product(range(2), repeat=H-1):
    candidate = []
    if any(i):
        start = 1
        for j, k in enumerate(i, start=1):
            if k:
                candidate.append((start, j))
                start = j+1
        candidate.append((start, H))
    else:
        candidate.append((1, H))
    
    q = [1]
    cutx = 0

    while q:
        s = q.pop()
        for t in range(s, W+1)[::-1]:
            if all(f(s, j, t, k)<=K for j, k in candidate):
                if t!=W:
                    q.append(t+1)
                    cutx += 1
                break
        else:
            cutx = H*W
    v = cutx+sum(i)
    ans = min(ans, v)

print(ans)

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    h,w,k=map(int,input().split())
    S=[input() for _ in range(h)]
    final_ans=10**10
    for row_lis in range(1<<(h-1)):
        lst=[0]*h
        q,ans=0,0
        for r in range(h-1):
            if (row_lis>>r)&1==0:
                lst[r+1]=q
            else:
                q+=1
                lst[r+1]=q
                ans+=1
        data=[0]*h
        for j in range(w):
            for i in range(h):
                data[lst[i]]+=int(S[i][j])
                if data[lst[i]]>k:
                    ans+=1
                    break
            else:
                continue
            data=[0]*h
            for i in range(h):
                data[lst[i]]+=int(S[i][j])
                if data[lst[i]]>k:
                    break
            else:
                continue
            break
        else:
            final_ans=min(final_ans,ans)
    print(final_ans)


def __starting_point():
    main()
__starting_point()

f=range
h,w,k=map(int,input().split())
g=[[int(i) for i in 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)

import sys
from itertools import product

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, K = list(map(int, input().split()))
    grid = [list(input()) for _ in range(H)]

    R = [[0] * (W + 1) for _ in range(H + 1)]
    for h in range(H):
        for w in range(W):
            R[h + 1][w + 1] = R[h][w + 1] + R[h + 1][w] - R[h][w] + int(grid[h][w])

    res = f_inf
    for pattern in product([0, 1], repeat=H-1):
        cut_H = [idx + 1 for idx, p in enumerate(pattern) if p == 1] + [H]
        cnt_cut = sum(pattern)
        left = 0
        right = 1
        flg = 1
        while right <= W:
            if not flg:
                break
            up = 0
            for bottom in cut_H:
                cnt_w = R[bottom][right] - R[bottom][left] - R[up][right] + R[up][left]
                if cnt_w > K:
                    if right - left == 1:
                        flg = False
                    cnt_cut += 1
                    left = right - 1
                    break
                else:
                    up = bottom
            else:
                right += 1
        else:
            res = min(res, cnt_cut)
    print(res)


def __starting_point():
    resolve()

__starting_point()

from itertools import *

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

cut_min = H+W-2

for r_cut in range(H):
  if cut_min <= r_cut:
    continue
  for r_pos in combinations(list(range(1, H)), r_cut):
    r_pos = (None,)+r_pos+(None,)
    r_blocks = [slice(*r_pos[i:i+2]) for i in range(len(r_pos)-1)]
    
    cut = r_cut
    prev_sum = [0] * len(r_blocks)
    for col in zip(*S):
      curr_sum = [sum(col[b]) for b in r_blocks]
      if any(map(K.__lt__, curr_sum)):
        break
      next_sum = [x+y for x,y in zip(prev_sum, curr_sum)]
      if any(map(K.__lt__, next_sum)):
        cut += 1
        if cut_min <= cut:
          break
        prev_sum = curr_sum
      else:
        prev_sum = next_sum
    else:
      cut_min = cut
print(cut_min)


h,w,kk=list(map(int,input().split()))
s=[list(map(int,list(input()))) for i in range(h)]
l=[]
for i in range(2**(h-1)):
  ll=[0]
  for j in range(h-1):
    if i & 2**j:
      ll.append(ll[-1]+1)
    else:
      ll.append(ll[-1])
  l.append(ll)

mc=w+h
for i in l:
  c=[0 for i in range(h)]
  cc=0
  f=1
  #print(i,0)
  for j in range(w):
    #print(c)
    ff=0
    for k in range(h):
      c[i[k]]+=s[k][j]
    for k in range(h):
      if c[k]>kk:
        ff=1
        break
    if ff:
      cc+=1
      c=[0 for i in range(h)]
      for k in range(h):
        c[i[k]]+=s[k][j]
      for k in range(h):
        if c[k]>kk:
          f=1
      if f:
        cc=w+h
        #print(c)
        break
    f=0
  #print(cc)
  if mc>cc+len(set(i))-1:
    mc=cc+len(set(i))-1
print(mc)

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)

def z(z_dic, v: int):
    if v in z_dic:
        return z_dic[v]
    z = 0
    if v == 2:
        z = 1
    elif v > 2:
        z = int(v*(v-1)/2)
    z_dic.setdefault(v, z)
    return z


def main():
    h, w, _k = list(map(int, input().split()))
    s = []
    for i in range(h):
        line = input()
        s_line = []
        for j in range(w):
            s_line.append(int(line[j]))
        s.append(s_line)

    ok_cnt_min = h*w
    op_cnt = h - 1  # すき間の個数
    for i in range(2 ** op_cnt):
        op = [False] * op_cnt
        for j in range(op_cnt):
            if ((i >> j) & 1):
                op[op_cnt - 1 - j] = True

        s2 =[]
        current_sum = s[0]
        for k in range(op_cnt):
            if op[k]:
                s2.append(current_sum)
                current_sum = s[k+1]
            else:
                next_sum = [(current_sum[a] + s[k+1][a]) for a in range(w)]
                current_sum = next_sum

        s2.append(current_sum)
        s2len = len(s2)

        h_cut_cnt = len([x for x in op if x])
        if h_cut_cnt >= ok_cnt_min:
            break

        st = 0
        ed = 1
        cut_list = []
        dividable = True
        for j in range(1, w+1):
            _sum_max = 0
            if ed <= j:
                ed = j
            else:
                continue

            _sum_max = max([sum(s2[_h][st:ed]) for _h in range(s2len)])
            if _sum_max > _k:
                if ed - st > 1:
                    cut_list.append(ed - 1)
                    st = ed - 1
                else:
                    dividable = False
                    break
        if not dividable:
            continue
        else:
            cnt = h_cut_cnt
            cnt += len(cut_list)
            if cnt < ok_cnt_min:
                ok_cnt_min = cnt

    print(ok_cnt_min)



main()


import numpy as np
from itertools import product
H, W, K = map(int, input().split())
G = np.array([list(map(int, input())) for _ in range(H)])
 
ans = float('inf')

for pattern in product([0, 1], repeat=H - 1):
    # スライスで横方向への割り方を表現する
    div=[0]
    for i, p in enumerate(pattern):
      if p==1:
        div= div+[i+1]
    div += [10]       
    
     # 横方向へ割った後、各ブロックについて縦方向にホワイトチョコの数を修正
    rows = []
    for i in range(len(div) - 1):
        rows.append(np.sum(G[div[i]: div[i + 1]], axis=0))
    
     # 縦方向にすでにK個より多いホワイトチョコが含まれている場合はどうにもならない
    count=0
    for r in rows:
      if np.any(r>K):
        count=1
    if count==1:
      continue
    
    # 縦方向に貪欲に割っていく
    rows = [r.tolist() for r in rows]
    tmp_ans = 0
    counts = [0] * len(rows)
    w = 0
    
    while w<W:
      for r in range(len(rows)):
        counts[r] += rows[r][w]
        
      if any([c>K for c in counts]):
        counts=[0] * len(rows)
        w -=1
        tmp_ans += 1
      
      w+=1
    a=tmp_ans +len(div)-2
    ans=min(a,ans)
  
print(ans)

from itertools import accumulate as acc

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

acc_list = [list(acc([0] + s)) for s in S]

def solve(l, x, limit):
    part_num = len(l)-1
    ok, ng = x, W+1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        score = 0
        for i in range(part_num):
            s = 0
            for j in range(l[i], l[i+1]):
                # print(i, j, mid)
                s += acc_list[j][mid] - acc_list[j][x]
            score = max(s, score)
        if score <= limit:
            ok = mid
        else:
            ng = mid
    return ok

min_num = 10**18
for i in range(1<<(H-1)):
    l = []
    for j in range(H-1):
        if (i>>j)&1:
            l.append(j+1)
    h_split_num = len(l)
    l = [0] + l + [H]
    x = solve(l, 0, K)
    w_split_num = 0
    flag = True
    while x < W:
        w_split_num += 1
        r = solve(l, x, K)
        if x == r:
            flag = False
            break
        x = r
    if flag:
        split_num = w_split_num + h_split_num
        min_num = min(split_num, min_num)

print(min_num)


import itertools

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

ans = 2000
#itertoolsproductでビット全探索が簡潔に書ける
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    #横方向の分割の回数を数えている
    lst = [[s for s in S[0]]]
    #リストを新たな要素として加えるか、それとも中身を足し合わせるだけか
    for h in range(H - 1):
        if t[h]:
            lst.append(S[h + 1])
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
    L = len(lst)
    sum_lst = [0] * L
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
        #横方向の分割を終えた時点で一列にK+1個以上あるとアウト
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp
    else:
        ans = min(ans, cnt)
print(ans)
#このコードはループをうまくリストに入れ込んでるので短く見えてすごい
#5月24日


import itertools
 
H,W,K=list(map(int, input().split()))
S=[]
for _ in range(H):
  S.append([int(s) for s in input()])
 
ans=2000
for t in itertools.product([0,1],repeat=H-1):
  cnt=t.count(1)
  lst=[[s for s in S[0]]]
  for h in range(H - 1):
    if t[h]==1:
      lst.append(S[h+1])
    else:
      lst[-1]=[lst[-1][i]+S[h+1][i] for i in range(W)]
  L=len(lst)
  R=[0]*L
  for w in range(W):
    if max(lst[i][w] for i in range(L))>K:
      break
    tmp=[R[i]+lst[i][w] for i in range(L)]
    if max(tmp)>K:
      cnt+=1
      R=[lst[i][w] for i in range(L)]
    else:
      R=tmp
  else:
    ans=min(ans,cnt)
print(ans)


def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    INF = 10**9

    H, W, K = map(int, input().split())
    chocolate = [ input() for _ in range(H) ]
    
    loop_H = range(H)
    min_cut = INF-1
    for div in range(1 << (H-1)):
        # 横割りでグループ分け
        group = [[]]
        group_number = 0
        for i in loop_H:
            group[group_number].append(i)
            if div >> i & 1:
                group.append([])
                group_number += 1
        # 縦に切っていく
        cut = group_number
        cnt = [0] * len(group)
        w = 0
        while w < W:
            now = [0] * len(group)
            for g in range(len(group)):
                for i in group[g]:
                    if chocolate[i][w] == '1':
                        now[g] += 1
                if now[g] > K:
                    cut = INF
                    break
                if cnt[g] + now[g] > K:
                    cut += 1
                    w -= 1
                    cnt = [0] * len(group)
                    break
                cnt[g] += now[g]
            if cut >= min_cut:
                break
            w += 1
        if cut < min_cut:
            min_cut = cut
    print(min_cut)

main()