CodeEff/ECCO huggingface dataset:
# Original solution
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1

        for i in range(W):
            f = False
            for j in range(H):
                for wii in range(ni + 1):
                    if j in wi[wii]:
                        if wn[wii] + int(S[j][i]) > K:
                            tmp += 1
                            f = True
                        else:
                            wn[wii] += int(S[j][i])
                            break
                if f:
                    break
            if f:
                for wii in range(ni + 1):
                    wn[wii] = 0
                for j in range(H):
                    for wii in range(ni + 1):
                        if j in wi[wii]:
                            wn[wii] += int(S[j][i])
                            break

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1

        for i in range(W):
            f = False
            for j in range(H):
                for wii in range(ni + 1):
                    if j in wi[wii]:
                        if wn[wii] + int(S[j][i]) > K:
                            tmp += 1
                            f = True
                        else:
                            wn[wii] += int(S[j][i])
                        break
                if f:
                    break
            if f:
                for wii in range(ni + 1):
                    wn[wii] = 0
                for j in range(H):
                    for wii in range(ni + 1):
                        if j in wi[wii]:
                            wn[wii] += int(S[j][i])
                            break
                for wii in range(ni + 1):
                    if wn[wii] > K:
                        tmp = float("inf")

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()
# Original solution
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10
        wi = [set() for _ in range(10)]

        ni = 0
        for i in range(H):
            wi[ni].add(i)
            if n >> i & 1:
                ni += 1
                tmp += 1

        for i in range(W):
            f = False
            for j in range(H):
                for wii in range(ni + 1):
                    if j in wi[wii]:
                        if wn[wii] + int(S[j][i]) > K:
                            tmp += 1
                            f = True
                        else:
                            wn[wii] += int(S[j][i])
                        break
                if f:
                    break
            if f:
                for wii in range(ni + 1):
                    wn[wii] = 0
                for j in range(H):
                    for wii in range(ni + 1):
                        if j in wi[wii]:
                            wn[wii] += int(S[j][i])
                            break
                for wii in range(ni + 1):
                    if wn[wii] > K:
                        tmp = float("inf")

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    H, W, K = [int(x) for x in input().split()]
    S = [list(input().strip()) for _ in range(H)]

    ans = float("inf")

    for n in range(2 ** (H - 1)):
        tmp = 0
        wn = [0] * 10

        for i in range(H):
            if n >> i & 1:
                tmp += 1

        for i in range(W):
            f = False
            ni = 0
            for j in range(H):
                if wn[ni] + int(S[j][i]) > K:
                    tmp += 1
                    f = True
                    break
                else:
                    wn[ni] += int(S[j][i])
                if n >> j & 1:
                    ni += 1
            if f:
                if i == 0:
                    tmp = float("inf")
                for j in range(H):
                    wn[j] = 0
                ni = 0
                for j in range(H):
                    wn[ni] += int(S[j][i])
                    if wn[ni] > K:
                        tmp = float("inf")
                    if n >> j & 1:
                        ni += 1

        ans = min(ans, tmp)

    print(ans)


if __name__ == '__main__':
    main()
# Original solution
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m, K = na()
b = []
for i in range(n):
    b.append(ns())

ans = 999999999999999
for ptn in range(1<<m-1):
    lans = 0
    x = ptn
    while x > 0:
        lans += x&1
        x //= 2

    to = [0] * n
    for i in range(1,n):
        if ptn>>i-1&1:
            to[i] = i
        else:
            to[i] = to[i-1]
    f = [0] * n
    ok = True
    for j in range(m):
        plus = [0] * n
        for r in range(n):
            plus[to[r]] += ord(b[r][j])-ord("0")
            if plus[to[r]] > K:
                ok = False
                break

        if not ok: break
        reset = False
        for r in range(n):
            if f[r] + plus[r] > K:
                reset = True
        if reset:
            lans += 1
            f = plus
        else:
            for i in range(n):
                f[i] += plus[i]
    if not ok:
        continue
    ans = min(ans, lans)
print(ans)


# Optimized solution
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m, K = na()
b = []
for i in range(n):
    b.append(ns())

ans = 999999999999999
for ptn in range(1<<n-1):
    lans = 0
    x = ptn
    while x > 0:
        lans += x&1
        x //= 2

    to = [0] * n
    for i in range(1,n):
        if ptn>>i-1&1:
            to[i] = i
        else:
            to[i] = to[i-1]
    f = [0] * n
    ok = True
    o = ord("0")
    for j in range(m):
        plus = [0] * n
        for r in range(n):
            plus[to[r]] += ord(b[r][j])-o
            if plus[to[r]] > K:
                ok = False
                break

        if not ok:
            break
        reset = any(f[r] + plus[r] > K for r in range(n))
        if reset:
            lans += 1
            f = plus
        else:
            for i in range(n):
                f[i] += plus[i]
    if not ok:
        continue
    ans = min(ans, lans)
print(ans)
# Original solution
r=range;_,*s=open(0)
h,w,k=list(map(int,_.split()))
m=9e9
for i in r(1<<h-1):
  t,v,l=[],-1,1
  for j in r(h):
    if i>>j&1:t+=j+1,;l+=1
  t+=h,
  c=[0]*l
  for i in r(w):
    b=f=g=0;u=[]
    for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
    v+=f
    if f:c=u
  if~g:m=min(m,v+l)
print(m)

# Optimized solution
r=range;_,*s=open(0)
h,w,k=list(map(int,_.split()))
m=9e9
for i in r(1<<h-1):
 t,v,l=[],-1,1
 for j in r(h):
  if i>>j&1:t+=j+1,;l+=1
 t+=h,
 c=[0]*l
 for i in r(w):
  b=f=g=0;u=[]
  for j in r(l):d,b=sum(s[j][i]>"0"for j in r(b,t[j])),t[j];u+=d,;g|=d>k;c[j]+=d;f|=c[j]>k
  v+=f
  if f:c=u
 if not g:m=min(m,v+l)
print(m)
# Original solution
import sys
input = sys.stdin.readline

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

m = float('inf')
for i in range(1 << (H - 1)) :
  pos = [0] * H
  x = 0
  for j in range(H - 1) :
    if i & (1 << j) :
      x += 1
    pos[j+1] = x
      
  x = 0
  cnt = [0] * H
  ret = bin(i)[2:].count('1')
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        break
    else :
      x += 1
      
  m = min(m, ret)
  
print(m)

# Optimized solution
import sys
input = sys.stdin.readline

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

m = float('inf')
for i in range(1 << (H - 1)) :
  pos = [0] * H
  x = 0
  for j in range(H - 1) :
    if i & (1 << j) :
      x += 1
    pos[j+1] = x
  
  ret = x
  x = 0
  cnt = [0] * H
  flag = 0
  while x < W :
    for y in range(H) :
      cnt[pos[y]] += S[y][x]
      if cnt[pos[y]] > K :
        cnt = [0] * H
        ret += 1
        flag += 1
        break
    else :
      x += 1
      flag = 0
      
    if flag == 2 :
      ret = float('inf')
      break
  
  m = min(m, ret)
  
print(m)
# Original solution
x,*s=open(0)
h,w,k,*m=list(map(int,x.split()))
for b in range(512):
 r=t=j=0;d=[0]*h
 while j<w:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';x=d[c]>k
   if(t<j)&x:r+=1;t=j;d=[0]*h;break
   r+=x*h*w;c+=b>>i&1;i+=1
  else:j+=1
 while b:r+=b&1;b>>=1
 m+=r,
print((min(m)))

# Optimized solution
x,*s=open(0)
h,w,k,*m=list(map(int,x.split()))
b=512
while b:
 b-=1;r=t=j=0;d=[0]*h
 while j<w:
  i=c=0
  while h-i:
   d[c]+=s[i][j]>'0';y=t<j
   if d[c]>k:d=[0]*h;r+=1-~-y*h*w;t=j;j-=y;break
   c+=b>>i&1;i+=1
  j+=1
 m+=r+c,
print((min(m)))
# Original solution
import sys
input = sys.stdin.readline
H, W, K = list(map(int, input().split()))

choco = []
for i in range(H):
  s = input().strip()
  a = list(map(int, list(s)))
  choco.append(a)

def f(n):
  if n == 1:
    return [[0], [1]]
  a = f(n-1)
  na = []
  for v in a:
    na.append([0] + v)
    na.append([1] + v)
  return na

def min_split(h):
  sum_cnt = [0] * H
  num_split = 0
  for j in range(W):
    c = 0
    cnt = [0] * H
    for i in range(H):
      if choco[i][j] == 1:
        cnt[c] += 1
      if i < H-1 and h[i] == 1:
        c += 1
    new_cnt = [x + y for x, y in zip(sum_cnt, cnt)]
    if max(new_cnt) > K:
      num_split += 1
      sum_cnt = cnt
    else:
      sum_cnt = new_cnt
  return num_split + sum(h)

min_m = float('inf')
for h in f(H-1):
  m = min_split(h)
  min_m = min(min_m, m)
print(min_m)

# Optimized solution
import sys, itertools
input = sys.stdin.readline
H, W, K = list(map(int, input().split()))

choco = []
for i in range(H):
  s = input().strip()
  a = list(map(int, list(s)))
  choco.append(a)

def min_split(h):
  sum_cnt = [0] * H
  num_split = 0
  for j in range(W):
    c = 0
    cnt = [0] * H
    flag = False
    for i in range(H):
      if choco[i][j] == 1:
        cnt[c] += 1
        if cnt[c] > K:
          return float('inf')
        if cnt[c] + sum_cnt[c] > K:
          flag = True
      if i < H-1 and h[i] == 1:
        c += 1
    if flag:
      num_split += 1
      sum_cnt = cnt
    else:
      for i in range(len(cnt)):
      	sum_cnt[i] += cnt[i]
  return num_split + sum(h)

min_m = float('inf')
for h in itertools.product([0,1], repeat=H-1):
  m = min_split(h)
  min_m = min(min_m, m)
print(min_m)
# Original solution
import sys
from itertools import accumulate

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

H, W, K = lr()
S = [list(map(int, sr())) for _ in range(H)]
Scum = [list(accumulate(x)) for x in S]
answer = 10000
for bit in range(1<<(H-1)):
    count = 0
    for i in range(H-1):
        if bit >> i & 1:
            count += 1
    bit += 1 << H-1 # 最後の切れ目
    # 縦のラインは貪欲法
    prev = -1
    w = 0
    while w < W:
        white = 0
        cut = False
        for i in range(H):
            white += Scum[i][w] - (Scum[i][prev] if prev >= 0 else 0)
            if (bit >> i) & 1: # 切れ目が来た
                if white > K:
                    cut = True
                white = 0
        if cut:
            if prev == w-1: # 一列でKをオーバー
                break
            count += 1
            prev = w-1
        else:
            w += 1
    else:
        answer = min(answer, count)

print(answer)


# Optimized solution
# coding: utf-8
import sys
from itertools import accumulate

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

H, W, K = lr()
S = [list(map(int, sr())) for _ in range(H)]
Scum = [list(accumulate(row)) for row in S]
# H方向はbit全探索、W方向はGreedyに
INF = 10 ** 10
answer = INF
for pattern in range(1<<(H-1)):
    slice = set()
    cnt = 0
    for i in range(H-1):
        if pattern>>i & 1:
            slice.add(i)
            cnt += 1
    slice.add(H-1)  # 最後の区切り
    w = 0
    prev = -1
    while w < W:
        cut = False
        white = 0
        for i in range(H):
            white += Scum[i][w] - (Scum[i][prev] if prev >= 0 else 0)
            if i in slice:
                if white > K:
                    cut = True
                    break
                white = 0
        if cut:
            if prev == w - 1:  # 1列でKをオーバーしたので無理
                break
            cnt += 1
            prev = w-1
        else:
            w += 1
    else:
        answer = min(answer, cnt)

print(answer)
# 43
# Original solution
import sys
input = sys.stdin.readline

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]
# print(s)
# print(len(s[1]))

# ans = h + w - 2
ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    #print(len(new_s))
    total = [0] * len(new_s)
    #print(new_s)
    for k in range(w):
        # print(k)
        tmp_list = [0]*len(new_s)
        #print(total)
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                cnt = 10**18
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
        if flag:
            break
        for m in total:
            flag_2 = 1
            if m > K:
                cnt += 1
                total = tmp_list
                flag_2 = 0
                break
        # if flag_2:
        #     for m in total:
        #         if m == K and k != w - 1:
        #             cnt += 1
        #             total = [0]*len(new_s)
        #             break
    if not flag:
        #print(cnt)
        ans = min(ans, cnt)
print(ans)






# Optimized solution
import sys
input = sys.stdin.readline

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]

ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    total = [0] * len(new_s) # ブロックごとに、切った後~進んだ分の増えたホワイトチョコの個数を管理
    for k in range(w):
        tmp_list = [0]*len(new_s) # ブロックごとに、1つ進めて増えるホワイトチョコを管理
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            if tmp > K:
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
        if flag:
            break
        for m in total: # 1つでもKを越えていたら直前で切る
            if m > K:
                cnt += 1
                total = tmp_list
                break
    if not flag:
        ans = min(ans, cnt)
print(ans)
# Original solution
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

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

ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      #境目のカウントに+1
                group_num+=1
            GROUP[i]=group_num

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    break_flag=False
    for w in range(W):
        if break_flag:  #breakフラグがTrueならループを止める
            break
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        #現在の集計でKを超えている値がないかをチェック
        for v in list(VALUE.values()):
            if v<=K:
                pass
            else:
                if ok is None:      #okに値がない場合は、このパターンは成り立たない
                    cnt=float("inf")    #不可能なパターンなのでカウントに無限大を代入
                    break_flag=True     #breakフラグにTrueを代入
                    break
                else:      #以前の列でok番号に値が入っていた、つまり成り立つ列があった場合
                    cnt+=1      #境目のカウントに+1
                    VALUE=defaultdict(lambda: 0)    #NGの場合は値を初期化して入れなおし
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w    #値が全てK以下だった場合はok変数に列番号を記録
    ans=min(ans,cnt)
       
print(ans)

# Optimized solution
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

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

ans=float("inf")
for bit in range(2**H):
    cnt=0
    group_num=0
    GROUP={}
    for i,s in enumerate(S):
        if i==0:
            GROUP[i]=group_num
        else:
            if bit>>i-1&1==1:
                cnt+=1      #境目のカウントに+1
                group_num+=1
            GROUP[i]=group_num

    ok=None
    VALUE=defaultdict(lambda: 0)
    w=0
    break_flag=False
    for w in range(W):
        if break_flag:  #breakフラグがTrueならループを止める
            break
        for h in range(H):
            VALUE[GROUP[h]]+=int(S[h][w])
        #現時点の集計でKを超えている値がないかをチェック
        for v in list(VALUE.values()):
            if v<=K:
                pass
            else:
                if ok is None:      #okに値がない場合は、このパターンは成り立たない
                    cnt=float("inf")    #不可能なパターンなのでカウントに無限大を代入
                    break_flag=True     #breakフラグにTrueを代入
                    break
                else:      #以前の列でok番号に値が入っていた、つまり成り立つ列があった場合
                    cnt+=1      #境目のカウントに+1
                    VALUE=defaultdict(lambda: 0)    #NGの場合は値を初期化して入れなおし
                    for h in range(H):
                        VALUE[GROUP[h]]+=int(S[h][w])
                    break
        else:
            ok=w    #値が全てK以下だった場合はok変数に列番号を記録
    ans=min(ans,cnt)
       
print(ans)
# Original solution
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))
        exit()

    # 横線の決め方を全探索
    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 impossible:
            x = 10**6

        ans = min(ans, x + ly)

    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
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))
        exit()

    # 横線の決め方を全探索
    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)


if __name__ == "__main__":
    main()