AtCoder Beginner Contest 159 - Dividing Chocolate

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.

Source: atcoder | Difficulty: MEDIUM


Solutions:
import itertools
(H, W, K) = list(map(int, input().split()))
S = [list(map(int, input())) for _ in range(H)]
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_)
print(ans)


import sys
(h, w, k) = [int(i) for i in sys.stdin.readline().split()]
s_ls = {}
for i in range(h):
	s_ls[i] = [int(j) for j in sys.stdin.readline().strip()]
best = h - 1 + w - 1
for i in range(1 << h - 1):
	flg = True
	s = bin(i)[2:].zfill(h - 1)
	ls = {i for (i, j) in enumerate(s) if j == '1'}
	dict = {i: 0 for i in range(len(ls) + 1)}
	cnt = 0
	for _w in range(w):
		j = 0
		col_sums = {i: 0 for i in range(len(ls) + 1)}
		for _h in range(h):
			val = s_ls[_h][_w]
			col_sums[j] += val
			dict[j] += val
			if _h in ls:
				j += 1
		if max(dict.values()) > k:
			cnt += 1
			dict = col_sums
		if max(col_sums.values()) > k:
			flg = False
		if not flg:
			break
	if flg:
		best = min(best, cnt + len(ls))
print(best)


from itertools import product

def makelist(BIT):
	(LIST, tmp) = ([], s[0])
	for (i, bi) in enumerate(BIT, 1):
		if bi == 1:
			LIST.append(tmp)
			tmp = s[i]
		elif bi == 0:
			tmp = [p + q for (p, q) in zip(tmp, s[i])]
	else:
		LIST.append(tmp)
	return LIST

def solve(LIST):
	(CNT, tmp) = (0, [l[0] for l in LIST])
	if any((num > k for num in tmp)):
		return h * w
	for i in range(1, w):
		cal = [tmp[j] + LIST[j][i] for j in range(len(LIST))]
		if any((num > k for num in cal)):
			CNT += 1
			tmp = [l[i] for l in LIST]
		else:
			tmp = cal
	return CNT
(h, w, k) = 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)


ans = 10 ** 8
(h, w, K) = map(int, input().split())
s = []
import copy

def two(x):
	return '0' * (h - 1 - len(bin(x)[2:])) + bin(x)[2:]
for i in range(h):
	s.append(input())
for i in range(2 ** (h - 1)):
	r = two(i)
	pre_ans = r.count('1')
	d = [0] * (pre_ans + 1)
	dd = copy.copy(d)
	cnt = 0
	for j in range(w):
		now = 0
		for k in range(h):
			if s[k][j] == '1':
				d[now] += 1
			if k != h - 1:
				if r[k] == '1':
					now += 1
		if max(d) > K:
			e = []
			for x in range(len(d)):
				e.append(d[x] - dd[x])
			d = copy.copy(e)
			cnt += 1
		if max(d) > K:
			cnt = 10 ** 7
		dd = copy.copy(d)
	pre_ans += cnt
	ans = min(ans, pre_ans)
print(ans)


(x, *s) = open(0)
(h, w, k, *m) = 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))


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) = 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)


(h, w, k) = map(int, input().split())
S = [list(map(int, input())) for _ in range(h)]
min_v = 10 ** 18
for i in range(2 ** (h - 1)):
	cnt = [0] * h
	row = [0] * h
	splt_cnt = 0
	splt = [0] * (h - 1)
	find = 1
	for j in range(h - 1):
		if i >> j & 1:
			splt[j] = 1
	for x in range(1, h):
		if splt[x - 1] == 0:
			row[x] = row[x - 1]
		elif splt[x - 1] == 1:
			row[x] = row[x - 1] + 1
	for c in range(w):
		for r in range(h):
			cnt[row[r]] += S[r][c]
		if max(cnt) > k:
			cnt = [0] * h
			splt_cnt += 1
			for r in range(h):
				cnt[row[r]] += S[r][c]
			if max(cnt) > k:
				find = 0
	splt_cnt += sum(splt)
	if splt_cnt < min_v and find:
		min_v = splt_cnt
print(min_v)


(H, W, K) = map(int, input().split())
S = [[int(c) for c in input()] for i in range(H)]
A = [[0] * (W + 1) for i in range(H + W)]
for i in range(H):
	for j in range(W):
		A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1] - A[i][j] + S[i][j]
from itertools import product
r = 2000

def v(l, r, t, b):
	return A[b][r] - A[t][r] - A[b][l] + A[t][l]
for x in product((0, 1), repeat=H - 1):
	l = 0
	a = sum(x)
	for j in range(W):
		f = 1
		t = 0
		for k in range(H - 1):
			if x[k]:
				if v(l, j + 1, t, k + 1) > K:
					f = 2 if l < j else 0
					l = j
				t = k + 1
		if v(l, j + 1, t, H) > K:
			f = 2 if l < j else 0
			l = j
		if f == 2:
			a += 1
		elif f == 0:
			a = -1
			break
	if a >= 0:
		r = min(r, a)
print(r)


import sys
from itertools import accumulate
readline = sys.stdin.readline
INF = 10 ** 9
(h, w, k) = map(int, readline().split())
s = [readline() for _ in range(h)]
ans = INF
for bit in range(2 ** h - 1):
	cut = bin(bit).count('1')
	group = 0
	peace = [[0] * (bin(bit).count('1') + 1) for _ in range(w)]
	for i in range(w):
		group = 0
		for j in range(h):
			if s[j][i] == '1':
				peace[i][group] += 1
			if bit >> j & 1:
				group += 1
	if any((max(col) > k for col in peace)):
		continue
	current = [0] * (bin(bit).count('1') + 1)
	for i in range(w):
		current = list(map(sum, zip(current, peace[i])))
		if max(current) > k:
			cut += 1
			current = peace[i]
	if ans > cut:
		ans = cut
print(ans)


from itertools import product
(H, W, K) = map(int, input().split())
S = [[int(i) for i in input()] for _ in range(H)]
T = [t for t in zip(*S)]
if sum(map(sum, T)) <= K:
	print(0)
	quit()
ans = float('inf')
for P in product([0, 1], repeat=H - 1):
	cnt = sum(P)
	if cnt >= ans:
		continue
	II = [[0]]
	for (i, p) in enumerate(P, 1):
		if p:
			II.append([])
		II[-1].append(i)
	A = [0] * len(II)
	for t in T:
		for (i, I) in enumerate(II):
			A[i] += sum((t[x] for x in I))
		if any((a > K for a in A)):
			cnt += 1
			if cnt >= ans:
				break
			A = [sum((t[x] for x in I)) for I in II]
			if any((a > K for a in A)):
				cnt = 1 + ans
				break
	ans = min(ans, cnt)
print(ans)


(h, w, K) = map(int, input().split())
s = [list(input()) for i in range(h)]
from itertools import groupby
ans = 10 ** 18
for i in range(1 << h):
	pre = -1
	c = []
	t_cnt = 0
	op = [-1] * h
	for j in range(h):
		if i & 1 << j:
			op[j] = 1
		else:
			op[j] = 0
	gr = groupby(op)
	l = []
	for (key, g) in gr:
		l.append(len(list(g)))
	c = [[0] * w for _ in range(len(l))]
	idx = 0
	jdx = 0
	for (idx, li) in enumerate(l):
		for k in range(li):
			for a in range(w):
				c[idx][a] += int(s[jdx][a])
			jdx += 1
	t_cnt = len(c) - 1
	t_cnt1 = 0
	c_mx = [0] * len(c)
	ok = True
	for a in range(w):
		for b in range(len(c)):
			if c[b][a] > K:
				ok = False
			c_mx[b] += c[b][a]
			if c_mx[b] > K:
				t_cnt1 += 1
				c_mx = [0] * len(c)
				for b in range(len(c)):
					c_mx[b] += c[b][a]
				break
	if ok:
		ans = min(ans, t_cnt + t_cnt1)
if ans == 10 ** 18:
	print(0)
else:
	print(ans)


(H, W, K) = map(int, input().split())
S = [input() for _ in range(H)]
d = 2 ** (H - 1)
mcut = 1008
for i in range(d):
	L = [0 for _ in range(H)]
	for j in range(1, H):
		L[j] = L[j - 1] + i % 2
		i //= 2
	C = [0 for _ in range(L[H - 1] + 1)]
	(cutp, cutq) = (True, True)
	cut = L[H - 1]
	for m in range(W):
		for l in range(H):
			C[L[l]] += int(S[l][m])
		if cutq:
			cutq = False
			if max(C) > K:
				cutp = False
				break
		elif max(C) > K:
			cut += 1
			C = [0 for _ in range(L[H - 1] + 1)]
			for l in range(H):
				C[L[l]] += int(S[l][m])
		if cutp == False:
			break
	if cutp:
		if cut < mcut:
			mcut = cut
print(mcut)


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()


import itertools
(H, W, K) = map(int, input().split())
S = [input() for _ in range(H)]
ans = 10000.0
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

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 copy
(H, W, K) = map(int, input().split())
S = []
for _ in range(H):
	S.append([int(x) for x in list(input())])
ans = H - 1 + (W - 1)
for i in range(2 ** (H - 1)):
	check = [0] * H
	for j in range(H - 1):
		if i >> j & 1:
			check[j + 1] = check[j] + 1
		else:
			check[j + 1] = check[j]
	g = check[H - 1] + 1
	A = [0] * g
	c = 0
	f = 0
	for j in range(W):
		B = [0] * g
		for k in range(H):
			if S[k][j] == 1:
				B[check[k]] += 1
			if B[check[k]] > K:
				c = 10 ** 4
				f = 1
				break
		if f:
			break
		for l in range(g):
			if B[l] == 0:
				continue
			elif A[l] + B[l] > K:
				c += 1
				A = copy.copy(B)
				break
			else:
				A[l] += B[l]
	ans = min(ans, c + g - 1)
print(ans)


def main():
	(H, W, K) = map(int, input().split())
	S = [input() for i in range(H)]
	ans = H * W
	for pat in range(2 ** (H - 1)):
		Cnt_sum = [0] * H
		ans_w = 0
		ans_h = bin(pat).count('1')
		fail = False
		for j in range(W):
			if fail:
				break
			s = 0
			Cnt = [0] * H
			for i in range(H):
				if S[i][j] == '1':
					Cnt[s] += 1
					Cnt_sum[s] += 1
				if Cnt[s] > K:
					fail = True
					break
				if 1 << i & pat > 0:
					s += 1
			if any([v > K for v in Cnt_sum]):
				ans_w += 1
				Cnt_sum = Cnt[:]
		else:
			ans = min(ans, ans_h + ans_w)
	print(ans)
main()


(h, w, k) = map(int, input().split())
s = [str(input()) for _ in range(h)]
p_ = [list(c) for c in s]
t = [[0] * h for _ in range(w)]
for i in range(h):
	for j in range(w):
		t[j][i] = int(p_[i][j])
ans = 10 ** 7
for i in range(2 ** (h - 1)):
	c = 0
	d = {}
	for j in range(h):
		d[j] = 0
	for j in range(h - 1):
		if i >> j & 1:
			d[j] = c
			c += 1
		else:
			d[j] = c
	d[h - 1] = c
	l = [0] * (c + 1)
	cnt = c
	for a in range(w):
		temp = [0] * (c + 1)
		for b in range(h):
			l[d[b]] += t[a][b]
			temp[d[b]] += t[a][b]
		if max(temp) > k:
			break
		if max(l) > k:
			cnt += 1
			l = temp
	else:
		ans = min(ans, cnt)
	continue
print(ans)


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)


from collections import defaultdict
from itertools import product
(H, W, K) = map(int, input().split())
S = [input() for i in range(H)]
C = [[int(S[i][k]) for i in range(H)] for k in range(W)]
answer = H * W
for X in product([True, False], repeat=H - 1):
	M = [[0]]
	ans = sum(X)
	if ans > answer:
		continue
	for (i, x) in enumerate(X):
		if x:
			M.append([])
		M[-1].append(i + 1)
	D = [0] * len(M)
	for c in C:
		for (k, m) in enumerate(M):
			D[k] += sum((c[i] for i in m))
		if any((d > K for d in D)):
			ans += 1
			if ans > answer:
				break
			D = [sum((c[i] for i in m)) for m in M]
			if any((d > K for d in D)):
				ans = answer + 1
				break
	answer = min(answer, ans)
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 = [[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()


(h, w, k) = map(int, input().split())
S = [input() for _ in range(h)]
ans = float('inf')
for bit in range(1 << h - 1):
	segment = [0] * h
	seg = 0
	for i in range(h - 1):
		if bit & 1 << i:
			seg += 1
		segment[i + 1] = seg
	n = max(segment) + 1
	count = n - 1
	k_cnt = [0] * n
	for j in range(w):
		tmp = [0] * n
		for i in range(h):
			k_cnt[segment[i]] += int(S[i][j])
			tmp[segment[i]] += int(S[i][j])
			if k_cnt[segment[i]] > k:
				count += 1
				for i in range(n):
					k_cnt[i] = tmp[i]
	ans = min(ans, count)
print(ans)


(H, W, K) = map(int, input().split())
S = [[int(i) for i in input()] for l in range(H)]
posibility = set()
for i in range(1 << H - 1):
	SW = []
	tmp = S[0]
	counter = 0
	for k in range(H - 1):
		if i >> k & 1:
			SW.append(tmp)
			tmp = S[k + 1]
		else:
			tmp = [tmp[l] + S[k + 1][l] for l in range(W)]
	SW.append(tmp)
	counter += len(SW) - 1
	max_counter = 0
	for k in range(len(SW)):
		max_counter = max(max(SW[k]), max_counter)
	if max_counter > K:
		continue
	tmp_w = [SW[row][0] for row in range(len(SW))]
	for w in range(W - 1):
		test = [tmp_w[row] + SW[row][w + 1] for row in range(len(SW))]
		if max(test) > K:
			tmp_w = [SW[row][w + 1] for row in range(len(SW))]
			counter += 1
		else:
			tmp_w = test
	posibility.add(counter)
print(min(posibility))


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

def nl(a, b):
	return [[0] * b for _ in range(a)]

def add(j):
	for i in range(g):
		now[i] += group_sum[i][j]
		if now[i] > K:
			return False
	return True
ans = float('inf')
for bit in range(1 << H - 1):
	id_of = [0] * H
	g = 0
	for i in range(H):
		id_of[i] = g
		if bit >> i & 1:
			g += 1
	g += 1
	count = g - 1
	group_sum = nl(H, W)
	for i in range(H):
		for j in range(W):
			group_sum[id_of[i]][j] += S[i][j]
	now = [0] * g
	for j in range(W):
		if not add(j):
			count += 1
			now = [0] * g
			if not add(j):
				count = float('inf')
				break
	ans = min(ans, count)
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()


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


(H, W, K) = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]
ans = 100000
for i in range(2 ** H):
	cnt = 0
	temp = i
	group = [0] * H
	for j in range(H):
		group[j] = cnt
		if temp & 1:
			cnt += 1
		temp >>= 1
	div = [0] * H
	for j in range(W):
		for k in range(H):
			if div[group[k]] + S[k][j] > K:
				cnt += 1
				div = [0] * H
				for l in range(H):
					div[group[l]] += S[l][j]
					if div[group[l]] > K:
						cnt = 100000
				break
			else:
				div[group[k]] += S[k][j]
	ans = min(ans, cnt)
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()


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()


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

def func(catyoko):
	cattate = 0
	past = [0] * 10
	for wi in range(w):
		now = [0] * 10
		for i in range(1, len(catyoko)):
			for j in range(catyoko[i - 1], catyoko[i]):
				now[i - 1] += s[j][wi]
		if max([past[i] + now[i] for i in range(10)]) > k:
			if max(now) > k:
				return -10
			else:
				cattate += 1
			past = [nowi for nowi in now]
		else:
			for i in range(10):
				past[i] += now[i]
	return cattate + len(catyoko) - 2
ans = h + w
for i in range(2 ** (h - 1)):
	catyoko = [0]
	for j in range(h - 1):
		if i >> j & 1:
			catyoko.append(j + 1)
	catyoko.append(h)
	a = func(catyoko)
	if a >= 0:
		ans = min(ans, a)
print(ans)


r = range
(h, *s) = open(0)
(h, w, k) = map(int, h.split())
m = 9000000000.0
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)


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]):
				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)


(h, w, k) = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]
ans = h * w
for div in range(1 << h - 1):
	row = 0
	S = [[0] * w]
	S[row] = [s[0][i] for i in range(w)]
	for i in range(1, h):
		if 1 & div >> i - 1:
			row += 1
			S.append([s[i][j] for j in range(w)])
		else:
			S[row] = [S[row][j] + s[i][j] for j in range(w)]
	count = [0] * (row + 1)
	ans_ = row
	a = True
	for i in range(w):
		for j in range(row + 1):
			if S[j][i] > k:
				a = False
				break
			count[j] += S[j][i]
			if count[j] > k:
				ans_ += 1
				count = [0] * (row + 1)
				for l in range(row + 1):
					count[l] += S[l][i]
				break
		if ans_ >= ans or a == False:
			break
	if a:
		ans = min(ans, ans_)
print(ans)


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)


(h, *s) = open(0)
(h, w, k, *m) = map(int, h.split())
b = w
while b:
	b -= 1
	r = 0
	t = j = w
	d = [0] * h
	while j:
		i = c = 0
		j -= 1
		while h - i:
			d[c] += s[i][j] > '0'
			c += b >> i & 1
			i += 1
			if max(d) > k:
				d = [0] * h
				r += 1
				(t, j) = (j, j + (t > j))
				i = h
	m += (r + c,)
print(min(m))


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


(H, W, K) = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]
accS = [[0] * (W + 1) for _ in range(H + 1)]
for h in range(H):
	for w in range(W):
		accS[h + 1][w + 1] = accS[h + 1][w] + accS[h][w + 1] - accS[h][w] + S[h][w]

def isOk(L, left, right):
	for (top, bot) in zip(L, L[1:]):
		if accS[bot][right] - accS[bot][left] - accS[top][right] + accS[top][left] > K:
			return False
	return True
ans = 10 ** 18
for mask in range(1 << H):
	L = [0] + [d + 1 for d in range(H - 1) if mask & 1 << d > 0] + [H]
	cnt = len(L) - 2
	left = 0
	while left < W:
		if not isOk(L, left, left + 1):
			cnt = 10 ** 18
			break
		right = left + 1
		while right < W and isOk(L, left, right + 1):
			right += 1
		cnt += 1
		left = right
	ans = min(ans, cnt - 1)
print(ans)


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)


(H, W, K) = map(int, input().split())
A = []
for i in range(H):
	a = list(map(int, list(input())))
	A.append(a)
ans = float('inf')
for i in range(2 ** (H - 1)):
	wtk = [0]
	cut = 0
	for j in range(H - 1):
		if i & 2 ** j > 0:
			wtk.append(wtk[-1] + 1)
			cut += 1
		else:
			wtk.append(wtk[-1])
	now = [0] * H
	for y in range(W):
		flag = True
		nnow = []
		for ll in now:
			nnow.append(ll)
		save = [0] * H
		for x in range(H):
			nnow[wtk[x]] += A[x][y]
			save[wtk[x]] += A[x][y]
		if max(save) > K:
			cut = float('inf')
			break
		if max(nnow) > K:
			cut += 1
			nnow = save
		now = nnow
	ans = min(ans, cut)
print(ans)


def inpl():
	return list(map(int, input().split()))

def solve(i):

	def getChoco(choco, w):
		for i in range(H):
			if S[i][w] == '1':
				choco[t[i]] += 1
		return choco
	t = {}
	t[0] = 0
	x = 0
	for h in range(H - 1):
		if (i >> h) % 2 == 1:
			x += 1
			t[h + 1] = x
		else:
			t[h + 1] = x
	choco = [0 for _ in range(x + 1)]
	ret = x
	for w in range(W):
		choco = getChoco(choco, w)
		if any((c > K for c in choco)):
			choco = getChoco([0 for _ in range(x + 1)], w)
			if any((c > K for c in choco)):
				return H + W - 2
			else:
				ret += 1
	return ret
(H, W, K) = inpl()
S = [input() for _ in range(H)]
ans = H + W - 2
for i in range(2 ** (H - 1)):
	ans = min(ans, solve(i))
print(ans)


(H, W, K) = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]
ans = float('inf')
for i in range(2 ** (H - 1)):
	kari = 0
	l = [0] * H
	if H > 1:
		for j in range(0, H - 1):
			if i >> j & 1:
				l[j + 1] = l[j] + 1
				kari += 1
			else:
				l[j + 1] = l[j]
	num = [0] * H
	for w in range(W):
		tmp = [0] * H
		for h in range(H):
			if S[h][w]:
				tmp[l[h]] += 1
		if max(tmp) > K:
			break
		if max([num[i] + tmp[i] for i in range(H)]) <= K:
			num = [num[i] + tmp[i] for i in range(H)]
		else:
			num = tmp
			kari += 1
	else:
		ans = min(ans, kari)
print(ans)


(h, w, k) = map(int, input().split())
ans = 10 ** 9
choco = [list(input()) for i in range(h)]
sumL = [[0 for i in range(w + 1)] for j in range(h + 1)]
for i in range(h):
	for j in range(w):
		sumL[i][j] = sumL[i - 1][j] + sumL[i][j - 1] - sumL[i - 1][j - 1] + int(choco[i][j])
for stat in range(2 ** (h - 1)):
	cnt = 0
	previous = -1
	flg = 0
	cut = format(stat, 'b').zfill(h - 1)
	cutl = []
	for hi in range(h - 1):
		if cut[hi] == '1':
			cutl.append(hi)
			cnt += 1
	cutl.append(h - 1)
	cutl.append(-1)
	for yoko in range(w):
		for seg in range(len(cutl)):
			if sumL[cutl[seg]][yoko] - sumL[cutl[seg]][previous] - sumL[cutl[seg - 1]][yoko] + sumL[cutl[seg - 1]][previous] > k and yoko - previous <= 1:
				flg = 1
			elif sumL[cutl[seg]][yoko] - sumL[cutl[seg]][previous] - sumL[cutl[seg - 1]][yoko] + sumL[cutl[seg - 1]][previous] > k:
				previous = yoko - 1
				cnt += 1
	if not flg and cnt < ans:
		ans = cnt
print(ans)


(H, W, K) = map(int, input().split())
S = [input() for _ in range(H)]
ans = 10 ** 5
for bit in range(2 ** (H - 1)):
	cur = [0] * H
	gnum = 0
	for i in range(H - 1):
		if not bit & 1 << i:
			cur[i + 1] = cur[i]
		else:
			cur[i + 1] = cur[i] + 1
			gnum += 1
	gok = True
	add = 0
	nums = [0] * (gnum + 1)
	for j in range(W):
		ones = [0] * (gnum + 1)
		ok = True
		for i in range(H):
			ones[cur[i]] += int(S[i][j])
			nums[cur[i]] += int(S[i][j])
			if ones[cur[i]] > K:
				gok = False
			if nums[cur[i]] > K:
				ok = False
		if not ok:
			add += 1
			nums = ones[:]
	if gok:
		ans = min(ans, gnum + add)
print(ans)


(h, w, K) = map(int, input().split())
g = [[0] * w for _ in range(h)]
for i in range(h):
	s = input()
	for j in range(w):
		g[i][j] = s[j]
ans = 1001001001
for i in range(1 << h - 1):
	seg = [0] * h
	segnow = 0
	for j in range(h - 1):
		if i & 1 << j:
			segnow += 1
		seg[j + 1] = segnow
	segnow += 1
	flag = True
	div = 0
	cnt = [0 for _ in range(segnow)]
	for j in range(w):
		now = [0] * segnow
		for k in range(h):
			if g[k][j] == '1':
				cnt[seg[k]] += 1
				now[seg[k]] += 1
				if cnt[seg[k]] > K:
					div += 1
					for l in range(segnow):
						cnt[l] = now[l]
		if max(now) > K:
			continue
	ans = min(ans, segnow - 1 + div)
print(ans)


(h, w, k) = map(int, input().split())
cho = [input() for i in range(h)]
size = [[0] * h for i in range(1 << h)]
ans = [bin(x).count('1') for x in range(1 << h)]
for stage in range(w):
	new = [[0] * h for i in range(1 << h)]
	for column in range(h):
		if int(cho[column][stage]):
			for bit in range(1 << h):
				length = ((1 << column) - 1 & bit).bit_length()
				new[bit][length] += 1
	for bit in range(1 << h):
		frag = True
		for column in range(h):
			if new[bit][column] + size[bit][column] > k:
				if new[bit][column] > k:
					ans[bit] += 1010
				frag = False
				ans[bit] += 1
				size[bit] = new[bit]
				break
		if frag:
			for column in range(h):
				size[bit][column] += new[bit][column]
print(min(ans))


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

def count(n):
	A = [0]
	c = 0
	i = 1
	while n:
		if n & 1:
			A.append(i)
			c += 1
		n >>= 1
		i += 1
	A.append(H)
	return (c, A)
ans = 2000
for n in range(1 << H - 1):
	(c, A) = count(n)
	X = [0] * (len(A) - 1)
	j = 0
	flag = True
	while j < W:
		for k in range(len(A) - 1):
			for i in range(A[k], A[k + 1]):
				if S[i][j] == '1':
					X[k] += 1
		for x in X:
			if x > K:
				if flag:
					c += 10000
					break
				flag = True
				c += 1
				X = [0] * (len(A) - 1)
				break
		else:
			flag = False
			j += 1
		if c > 10000:
			break
	ans = min(ans, c)
print(ans)


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())


import sys
(h, w, k) = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]
res = 0
ans = 10 ** 9
for i in range(2 ** (h - 1)):
	p = 1
	partation = [-1] * (h - 1)
	for j in range(h - 1):
		if i & 1 << j:
			partation[j] = 1
			p += 1
	g = [0] * p
	res = 0
	l = r = 0
	f = False
	while r < w:
		m = 0
		for j in range(h):
			g[m] += s[j][r]
			if g[m] > k:
				res += 1
				g = [0] * p
				if l == r:
					f = True
				l = r
				break
			if j < h - 1 and partation[j] == 1:
				m += 1
		else:
			r += 1
		if f:
			break
	else:
		res += p - 1
		if res < ans:
			ans = res
print(ans)


(h, w, k) = map(int, input().split())
a = [list(input()) for i in range(h)]
acc = [[0 for i in range(w + 1)] for j in range(h + 1)]
for i in range(1, h + 1):
	for j in range(1, w + 1):
		acc[i][j] = acc[i - 1][j]
		if a[i - 1][j - 1] == '1':
			acc[i][j] += 1
for i in range(1, h + 1):
	for j in range(1, w + 1):
		acc[i][j] += acc[i][j - 1]
ans = 1000000

def cut(x, y, up, left):
	return acc[x][y] - acc[x][left] - acc[up][y] + acc[up][left]
for i in range(2 ** (h - 1)):
	sep = [0]
	for r in range(h - 1):
		if i & 1 << r:
			sep.append(r + 1)
	sep.append(h)
	anstmp = len(sep) - 2
	left = 0
	for j in range(1, w):
		if max(list((cut(sep[x], j, sep[x - 1], left) for x in range(len(sep))))) > k:
			break
		if max(list((cut(sep[x], j + 1, sep[x - 1], left) for x in range(len(sep))))) > k:
			anstmp += 1
			left = j
	else:
		ans = min(ans, anstmp)
print(ans)


def main():
	import sys
	input = sys.stdin.readline
	(h, w, k) = map(int, input().split())
	S = []
	for _ in range(h):
		s = list(map(int, list(input().rstrip())))
		S.append(s)
	ans = 10 ** 5
	for i in range(2 ** (h - 1)):
		l = [0]
		for j in range(h - 1):
			if i & 1 << j:
				l.append(l[-1] + 1)
			else:
				l.append(l[-1])
		ans_ = l[-1]
		ll = [0] * h
		j = 0
		flag = 0
		while j < w:
			for p in range(h):
				ll[l[p]] += S[p][j]
			if max(ll) > k and flag == 0:
				flag = 1
				ans_ += 1
				ll = [0] * h
			elif max(ll) > k and flag == 1:
				ans_ = 10 ** 5
				break
			else:
				j += 1
				flag = 0
		ans = min(ans, ans_)
	print(ans)
main()


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()))

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()

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)
	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

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] * H
		for h in range(1, H):
			h_patterns[h] = h_patterns[h - 1] + h_divs[h - 1]
		div_cnt = h_patterns[-1]
		white_cnt = [0] * (div_cnt + 1)
		valid_div = True
		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
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)


def W_tips(j):
	global K, g, now, tips
	for i in range(g):
		now[i] += tips[i][j]
	for i in range(g):
		if now[i] > K:
			return False
	return True
f_inf = float('inf')
(H, W, K) = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
ans = f_inf
for div in range(1 << H - 1):
	g = 0
	tips = [[0] * W]
	tips[g] = [s + b for (s, b) in zip(S[0], tips[g])]
	for i in range(1, H):
		if div >> i - 1 & 1:
			g += 1
			tips.append([0] * W)
		tips[g] = [s + b for (s, b) in zip(S[i], tips[g])]
	num = g
	g += 1
	now = [0] * g
	for j in range(W):
		if W_tips(j) == False:
			num += 1
			now = [0] * g
			if W_tips(j) == False:
				num = f_inf
				break
	ans = min(ans, num)
print(ans)


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))
	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)


def make_bit(i):
	if i == h - 1:
		solve(t)
		return
	make_bit(i + 1)
	t[i] = 1
	make_bit(i + 1)
	t[i] = 0

def solve(u):
	global ans
	c = sum(u)
	x = [0] * (c + 1)
	y = [0] * h
	for i in range(h - 1):
		y[i + 1] = y[i] + u[i]
	for i in range(w):
		for j in range(h):
			x[y[j]] += int(s[j][i])
		if max(x) > k:
			c += 1
			x = [0] * c
			for j in range(h):
				x[y[j]] += int(s[j][i])
		if max(x) > k:
			c = 1919810
			break
	if ans > c:
		ans = c
	return
(h, w, k) = map(int, input().split())
s = [list(input()) for _ in range(h)]
t = [0] * (h - 1)
ans = 114514
make_bit(0)
print(ans)


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

def f(b, l, r):
	R = [0]
	for i in range(H):
		R[-1] += C[i][r + 1] - C[i][l]
		if i != H - 1:
			if b & 1 << i:
				R.append(0)
	return max(R)
INF = 10 ** 12
P = INF
Q = 0
L = 0
for x in range(1 << H - 1):
	Q = bin(x).count('1')
	L = 0
	for i in range(W):
		if f(x, L, i) > K:
			Q += 1
			L = i
			if f(x, L, i) > K:
				Q = INF
				break
	P = min(P, Q)
print(P)


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)
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)


def getChoco(choco, w, t):
	for h in range(H):
		if S[h][w] == '1':
			choco[t[h]] += 1
	return choco

def solve(i):
	t = dict()
	t[0] = 0
	g = 0
	for h in range(H - 1):
		if (i >> h) % 2 == 1:
			g += 1
			t[h + 1] = g
		else:
			t[h + 1] = g
	ret = g
	choco = [0 for _ in range(g + 1)]
	for w in range(W):
		choco = getChoco(choco, w, t)
		if any((c > K for c in choco)):
			choco = getChoco([0 for _ in range(g + 1)], w, t)
			if any((c > K for c in choco)):
				return 10 ** 9
			else:
				ret += 1
	return ret
(H, W, K) = map(int, input().split())
S = [input() for _ in range(H)]
ans = H + W - 2
for i in range(2 ** (H - 1)):
	ans = min(ans, solve(i))
print(ans)


(h, w, k) = map(int, input().split())
s = [[int(s_ij) for s_ij in input()] for _ in range(h)]
minimum = (h - 1) * (w - 1)
for div_h in range(1 << h - 1):
	h_index = [0] * h
	cur_index = 0
	mask = 1 << h - 2
	for i in range(1, h):
		if div_h & mask:
			cur_index += 1
		h_index[i] = cur_index
		mask >>= 1
	white_choco = [0] * (cur_index + 1)
	divide = 0
	j = 0
	flag = False
	while j < w:
		for i in range(h):
			white_choco[h_index[i]] += s[i][j]
		if max(white_choco) > k:
			if flag:
				break
			flag = True
			white_choco = [0] * (cur_index + 1)
			divide += 1
		else:
			j += 1
			flag = False
	else:
		minimum = min(minimum, divide + cur_index)
print(minimum)


(x, *s) = open(0)
(h, w, k, *m) = 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))


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
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()


(H, W, K) = map(int, input().split())
S = [input() for h in range(H)]
ans = float('inf')
for i in range(2 ** (H - 1)):
	_ans = bin(i).count('1')
	chocos = [list(map(int, S[0]))]
	for j in range(H - 1):
		if i >> j & 1:
			chocos.append(list(map(int, S[j + 1])))
		else:
			for w in range(W):
				chocos[-1][w] += int(S[j + 1][w])
	ns = len(chocos)
	nums = [0] * ns
	is_next = False
	for w in range(W):
		for j in range(ns):
			nums[j] += chocos[j][w]
			if chocos[j][w] > K:
				_ans = float('inf')
			if nums[j] > K:
				_ans += 1
				is_next = True
				break
		if is_next:
			for j in range(ns):
				nums[j] = chocos[j][w]
			is_next = False
	ans = min(ans, _ans)
print(ans)


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:
				break
			cnt += 1
			prev = w - 1
		else:
			w += 1
	else:
		answer = min(answer, cnt)
print(answer)


(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)):
	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):
		if h_cut & 2 ** (-i + h - 1):
			idx += 1
		temp_dict[i] = idx
	iw = 0
	while iw < w:
		for ih in range(h):
			count_white[temp_dict[ih]] += choco[ih][iw]
		condition = max(count_white) > k
		if condition:
			if w_last_cut_pos < iw - 1:
				num_cut += 1
				w_last_cut_pos = iw - 1
				count_white = [0] * (num_cut_yoko + 1)
			else:
				valid = False
				break
		else:
			iw += 1
	if valid:
		ans = min(ans, num_cut)
print(ans)


(h, w, k) = map(int, input().split())
s = []
for _ in range(h):
	s.append(input())
sum = [[0] * (w + 1) for _ in range(h + 1)]
for i in range(h):
	for j in range(w):
		sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + (1 if s[i][j] == '1' else 0)
ans = h + w - 2
for ptn in range(1 << h - 1):
	cand = 0
	sep = [0]
	for i in range(h - 1):
		if ptn >> i & 1:
			sep.append(i + 1)
			cand += 1
	sep.append(h)
	left = 0
	for pos in range(w):
		cur = []
		for i in range(len(sep) - 1):
			cur.append(sum[sep[i + 1]][pos + 1] - sum[sep[i + 1]][left] - sum[sep[i]][pos + 1] + sum[sep[i]][left])
		if max(cur) > k:
			if left == pos:
				cand = h * w
				break
			else:
				cand += 1
				left = pos
	ans = cand if cand < ans else ans
print(ans)


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 itertools
(H, W, K) = map(int, input().split())
A = [[int(x) for x in input()] for _ in range(H)]

def solve(blocks):
	n_block = len(blocks)
	n_cut = n_block - 1
	sums = [0 for _ in range(n_block)]
	for c in range(W):
		adds = [block[c] for block in blocks]
		if any((a > K for a in adds)):
			return H * W
		sums = [s + a for (s, a) in zip(sums, adds)]
		if any((s > K for s in sums)):
			n_cut += 1
			sums = adds
	return n_cut
ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
	mask = [1] + list(mask) + [1]
	pivots = [r for r in range(H + 1) if mask[r]]
	blocks = [A[p1:p2] for (p1, p2) in zip(pivots[:-1], pivots[1:])]
	blocks = [[sum((row[c] for row in block)) for c in range(W)] for block in blocks]
	ans = min(ans, solve(blocks))
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)
	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 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)

def greedy(W, S, K, horizons, current_answer):
	answer = sum(horizons)
	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]
		if max(current) > K:
			return float('INF')
		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()


(h, w, k) = list(map(int, input().split()))
s = [list(map(int, [x for x in input()])) for _ in range(h)]
cnt = 10001
for i in range(2 ** (h - 1)):
	split = [0] * h
	curcnt = 0
	for j in range(h):
		if i >> j & 1:
			split[j] = 1
			curcnt += 1
	nsplit = curcnt + 1
	sumlst = [[0] * nsplit for _ in range(w)]
	cw = 0
	memo = 0
	chk = 0
	flag = False
	while cw < w:
		l = 0
		for ch in range(h):
			sumlst[memo][l] += s[ch][cw]
			if sumlst[memo][l] > k:
				memo += 1
				chk += 1
				break
			if split[ch]:
				l += 1
		else:
			chk = 0
			cw += 1
			continue
		if chk > 1:
			break
	else:
		cnt = min(cnt, curcnt + memo)
print(cnt)


(h, w, k) = map(int, input().split())
f = [input() for _ in range(h)]
ans = 10 ** 18
for i in range(1 << h - 1):
	possible = True
	x = i
	cut = [0] * (h - 1)
	for j in range(h - 1):
		cut[j] = x & 1
		x >>= 1
	index = [0] * h
	for j in range(h - 1):
		index[j + 1] = index[j] + cut[j]
	n = index[h - 1] + 1
	s = [0 for _ in range(n)]
	ver = 0
	for j in range(w):
		need = False
		for z in range(h):
			s[index[z]] += int(f[z][j])
			if s[index[z]] > k:
				need = True
		if need:
			ver += 1
			s = [0 for _ in range(n)]
			for z in range(h):
				s[index[z]] += int(f[z][j])
				if s[index[z]] > k:
					possible = False
	if possible:
		ans = min(ans, sum(cut) + ver)
print(ans)


(h, w, k) = map(int, input().split())
board = [list(map(int, input())) for i in range(h)]
bitcnt = [0] * (1 << h)
for i in range(1 << h - 1):
	bitcnt[2 * i] = bitcnt[i]
	bitcnt[2 * i + 1] = bitcnt[i] + 1
ans = float('inf')
for state in range(1 << h - 1):
	s = [0] * h
	ans_tmp = 0
	can = True
	for i in range(w):
		cnt = 0
		tmp = [0] * h
		for j in range(h):
			tmp[cnt] += board[j][i]
			if state & 1 << j or j == h - 1:
				cnt += 1
		if any((tmp[j] > k for j in range(cnt))):
			can = False
			break
		if all((s[j] + tmp[j] <= k for j in range(cnt))):
			for j in range(cnt):
				s[j] += tmp[j]
		else:
			s = tmp
			ans_tmp += 1
	if can:
		ans = min(ans, ans_tmp + bitcnt[state])
print(ans)


def column_check(grp, grp_count, choco, h, j, k):
	curr_count = [0] * len(grp_count)
	for i in range(h):
		if choco[i][j] == '0':
			continue
		curr_count[grp[i]] += 1
	for cc in curr_count:
		if cc > k:
			return 2
	for (i, cc) in enumerate(curr_count):
		grp_count[i] += cc
		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))


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 chk(area):
	num = 0
	l = len(area)
	cnt = [0 for _ in range(l)]
	for i in range(w):
		for j in range(h):
			cnt[area[j]] += choko[i][j]
		if max(cnt) > k:
			if i > 0:
				num += 1
			cnt = [0 for _ in range(l)]
			for j in range(h):
				cnt[area[j]] += choko[i][j]
			if max(cnt) > k:
				return 10 ** 10
	return num
(h, w, k) = map(int, input().split())
s = [input() for _ in range(h)]
choko = [[int(s[i][j]) for i in range(h)] for j in range(w)]
area = [0 for i in range(h)]
ans = 10 ** 10
for v in range(0, 2 ** (h - 1)):
	p = bin(v)[2:].zfill(h - 1)
	for i in range(h - 1):
		if p[i] == '1':
			area[i + 1] = area[i] + 1
		else:
			area[i + 1] = area[i]
	tmp1 = sum([int(p[i]) for i in range(h - 1)]) + chk(area)
	ans = min(ans, tmp1)
print(ans)


(h, w, k) = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(h)]
ans = 10 ** 9 + 7
for i in range(1 << h - 1):
	group = [[0] * w]
	g_id = 0
	group[g_id] = [s + b for (s, b) in zip(S[0], group[0])]
	for j in range(1, h):
		if i >> j - 1 & 1:
			g_id += 1
			group.append([0] * w)
		group[g_id] = [s + b for (s, b) in zip(S[j], group[g_id])]
	if not all([all([i <= k for i in b]) for b in group]):
		continue
	cnt = len(group) - 1
	g_cnts = [0] * len(group)
	for jj in range(w):
		for g_id in range(len(group)):
			g_cnts[g_id] += group[g_id][jj]
		if any([c > k for c in g_cnts]):
			cnt += 1
			for g_id in range(len(group)):
				g_cnts[g_id] = group[g_id][jj]
	ans = min(ans, cnt)
print(ans)


(H, W, K) = map(int, input().split())
S = [list(map(int, list(input()))) for i in range(H)]
ans = float('inf')
for i in range(1 << H - 1):
	cnt = 0
	lst = [0] * H
	qqq = 0
	for j in range(H - 1):
		if i & 1 << j == 0:
			lst[j + 1] = qqq
			continue
		else:
			qqq += 1
			lst[j + 1] = qqq
			cnt += 1
	data = [0] * H
	for j in range(W):
		for k in range(H):
			data[lst[k]] += S[k][j]
			if data[lst[k]] > K:
				cnt += 1
				break
		else:
			continue
		data = [0] * H
		for k in range(H):
			data[lst[k]] += S[k][j]
			if data[lst[k]] > K:
				break
		else:
			continue
		break
	else:
		ans = min(ans, cnt)
print(ans)


(H, W, K) = map(int, input().split())
S = []
for _ in range(H):
	S.append([c for c in input()])
ans = float('inf')
for div in range(2 ** (H - 1)):
	g = 0
	ids = [0] * H
	for i in range(H):
		ids[i] = g
		if div >> i & 1:
			g += 1
	g += 1
	c = [[0 for _ in range(1005)] for _ in range(10)]
	for i in range(H):
		for j in range(W):
			c[ids[i]][j] += int(S[i][j])
	num = g - 1
	now = [0] * g

	def add(j):
		for i in range(g):
			now[i] += c[i][j]
			if now[i] > K:
				return False
		return True
	for j in range(W):
		if not add(j):
			num += 1
			now = [0] * g
			if not add(j):
				num = float('inf')
				break
	ans = min(ans, num)
print(ans)


(H, W, K) = map(int, input().split())
S = [list(map(int, list(input()))) for i in range(H)]
ans = H + W - 2
for bit in range(2 ** (H - 1)):
	divH = [0]
	for j in range(H - 1):
		if bit >> j & 1:
			divH.append(j + 1)
	divH.append(H)
	glen = len(divH) - 1
	group = [0] * glen
	res = glen - 1
	go = True
	w = 0
	while w < W:
		ok = True
		c = [0] * glen
		for g in range(glen):
			cum = 0
			for h in range(divH[g], divH[g + 1]):
				cum += S[h][w]
			c[g] += cum
			if cum > K:
				go = False
				break
			if c[g] + group[g] > K:
				ok = False
		if not go:
			break
		if not ok:
			res += 1
			group = [0] * glen
		else:
			for i in range(glen):
				group[i] += c[i]
			w += 1
	if not go:
		continue
	ans = min(ans, res)
print(ans)


(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]))
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)
	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(ans)


(h, w, K) = map(int, input().split())
s = [[int(i) for i in list(input())] for _ in range(h)]
ssum = [[0] * w for _ in range(h)]
for i in range(h):
	for j in range(w):
		if i == 0:
			ssum[i][j] = s[i][j]
		else:
			ssum[i][j] = ssum[i - 1][j] + s[i][j]

def cnt(line, i, j):
	if i == 0:
		return ssum[j - 1][line]
	else:
		return ssum[j - 1][line] - ssum[i - 1][line]
ans = 10 ** 6
for i in range(2 ** (h - 1)):
	l = [0]
	s = 0
	for j in range(h):
		if i >> j & 1:
			s += 1
			l.append(j + 1)
	l.append(h)
	d = [0] * (len(l) - 1)
	for j in range(w):
		nxt = [cnt(j, l[k], l[k + 1]) for k in range(len(l) - 1)]
		d2 = [nxt[i] + d[i] for i in range(len(l) - 1)]
		if max(nxt) > K:
			s = 10 ** 7
			break
		if max(d2) > K:
			d = nxt
			s += 1
		else:
			d = d2
	ans = min(ans, s)
print(ans)


(h, w, k) = map(int, input().split())
l = [[0 for i in range(w + 1)]] + [[0] + [int(j) for j in input()] for i in range(h)]
a = [[0 for i in range(w + 1)] for i in range(h + 1)]
for i in range(1, h + 1):
	for j in range(1, w + 1):
		a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + l[i][j]
ans = h * w

def ink(h2, h1, w2, w1):
	return a[h2][w2] - a[h1][w2] - (a[h2][w1] - a[h1][w1])
for i in range(2 ** (h - 1)):
	tl = [0]
	for j in range(h - 1):
		if i >> j & 1:
			tl.append(j + 1)
	tl.append(h)
	t = len(tl) - 2
	w1 = 0
	for w2 in range(1, w + 1):
		for (h1, h2) in zip(tl, tl[1:]):
			if ink(h2, h1, w2, w1) > k:
				if w2 - 1 == w1:
					t = h * w
					break
				w1 = w2 - 1
				t += 1
				break
	ans = min(ans, t)
print(ans)


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())))
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]

def isOk(x, lastq, cond, K, H, W):
	lastp = 0
	for j in range(H - 1):
		if cond >> 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)


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) = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]
ans = float('inf')
for sep in range(1 << h - 1):
	g_id = [0] * h
	cur = 0
	for i in range(h - 1):
		g_id[i] = cur
		if sep >> i & 1:
			cur += 1
	g_id[h - 1] = cur
	g_num = cur + 1
	ng = False
	for i in range(w):
		tmp = [0] * g_num
		for j in range(h):
			tmp[g_id[j]] += s[j][i]
		if any([x > k for x in tmp]):
			ng = True
			break
	if ng:
		continue
	res = g_num - 1
	gs = [0] * g_num
	for i in range(h):
		gs[g_id[i]] += s[i][0]
	for i in range(1, w):
		tmp = gs[:]
		for j in range(h):
			tmp[g_id[j]] += s[j][i]
		if any([x > k for x in tmp]):
			res += 1
			gs = [0] * g_num
		for j in range(h):
			gs[g_id[j]] += s[j][i]
	ans = min(ans, res)
print(ans)


(h, w, k) = map(int, input().split())
choco = []
mcut = h + w
for i in range(h):
	choco.append(list(map(int, list(input()))))
for i in range(2 ** (h - 1)):
	chocos = []
	cut = 0
	choco1 = choco[0][:]
	for j in range(h - 1):
		if i >> j & 1:
			chocos.append(choco1)
			choco1 = choco[j + 1][:]
			cut += 1
		else:
			for l in range(w):
				choco1[l] += choco[j + 1][l]
	chocos.append(choco1)
	num = len(chocos)
	chocosum = [0 for _ in range(num)]
	flag = True
	for j in range(w):
		for l in range(num):
			if chocos[l][j] > k:
				flag = False
			chocosum[l] += chocos[l][j]
			if chocosum[l] > k:
				cut += 1
				chocosum = [chocos[_][j] for _ in range(num)]
				break
	if flag:
		mcut = min(cut, mcut)
print(mcut)


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)


from itertools import product
(H, W, K) = map(int, input().split())
choco = [list(input()) for _ in range(H)]

def cnt(array):
	count = [0] * H
	split_cnt = 0
	for w in range(W):
		for h in range(H):
			if choco[h][w] == '1':
				count[array[h]] += 1
		if any((i > K for i in count)):
			split_cnt += 1
			count = [0] * H
			for h in range(H):
				if choco[h][w] == '1':
					count[array[h]] += 1
			if any((i > K for i in count)):
				return 10 ** 20
	return split_cnt

def get_array(array):
	l = len(array)
	ret = [0] * l
	for i in range(1, l):
		ret[i] = ret[i - 1] + array[i]
	return ret
ans = 10 ** 20
for p in product(range(2), repeat=H - 1):
	p = get_array([0] + list(p))
	ans = min(ans, cnt(p) + max(p))
print(ans)


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
		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()


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

def popcount(x):
	global h
	ret = 0
	for i in range(h - 1):
		ret += x >> i & 1
	return ret
ans = 1000000000000000
for i in range(2 ** (h - 1)):
	p = popcount(i)
	div = [0] * (p + 1)
	ans_sub = p
	f = False
	for j in range(w):
		now = 0
		div[now] += s[0][j]
		for l in range(h - 1):
			if i >> l & 1:
				now += 1
			div[now] += s[l + 1][j]
		if all((i <= k for i in div)):
			continue
		else:
			div = [0] * (p + 1)
			now = 0
			div[now] = s[0][j]
			for l in range(h - 1):
				if i >> l & 1:
					now += 1
				div[now] += s[l + 1][j]
			ans_sub += 1
			f = any((i > k for i in div))
	if not f:
		ans = min(ans, ans_sub)
print(ans)


(h, w, k) = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h * w <= k:
	result.append(0)
else:
	for i in range(2 ** (h - 1)):
		(checker, num) = (0, i)
		while num > 0:
			checker += num % 2
			num >>= 1
		x = 0
		c = [0 for _ in range(checker + 1)]
		for j in range(w):
			num = i
			p = 0
			nex = [0 for _ in range(checker + 1)]
			for m in range(h):
				nex[p] += s[m][j]
				p += num % 2
				num = num >> 1
			if max(nex) > k:
				x = 10 ** 5
				break
			if all((nex[m] + c[m] <= k for m in range(checker + 1))):
				c = [c[I] + nex[I] for I in range(checker + 1)]
			else:
				x += 1
				c = nex
		result.append(checker + x)
print(min(result))


(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

def input():
	return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = 1001001001
(H, W, K) = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
ans = INF
for b in range(1 << H - 1):
	g = 0
	idx = [0] * H
	for i in range(H - 1):
		if b >> i & 1:
			g += 1
		idx[i + 1] = g
	g += 1
	cnt = [[0] * W for _ in range(g)]
	for i in range(H):
		for j in range(W):
			cnt[idx[i]][j] += S[i][j]
	num = g - 1
	now = [0] * g

	def add(j):
		global now
		for i in range(g):
			now[i] += cnt[i][j]
			if now[i] > K:
				return False
		return True
	for j in range(W):
		if add(j) == False:
			num += 1
			now = [0] * g
			if add(j) == False:
				num = INF
				break
	ans = min(ans, num)
print(ans)


(H, W, K) = map(int, input().split())
A = [0] * H
for i in range(H):
	A[i] = input()
s = 10000
for i in range(2 ** (H - 1)):
	count = 0
	B = [0] * H
	B[H - 1] = 1
	for j in range(H - 1):
		if i >> j & 1:
			B[j] = 1
			count += 1
	C = [0] * (count + 1)
	for j in range(W):
		a = [0] * (count + 1)
		n = 0
		max = C[0]
		maxa = a[0]
		for k in range(H):
			a[n] += int(A[k][j])
			C[n] += int(A[k][j])
			if B[k] == 1:
				if max < C[n]:
					max = C[n]
				if maxa < a[n]:
					maxa = a[n]
				n += 1
		if max > K:
			count += 1
			C[:] = a[:]
		if maxa > K:
			count = 10000
			break
	if s > count:
		s = count
print(s)


import sys

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

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]
	res += len(s)
	s.append(H)
	y = 0
	for w in range(1, W + 1):
		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, kk) = map(int, input().split())
s = [list(map(int, input())) for i in range(h)]
ans = h + w - 2
for i in range(1 << h - 1):
	tate = 0
	index = [0] * h
	for j in range(h - 1):
		if i & 1 << j:
			tate += 1
		index[j + 1] = tate
	chocos = [0] * (tate + 1)
	yoko = 0
	ok = True
	for j in range(w):
		for k in range(h):
			chocos[index[k]] += s[k][j]
		if max(chocos) > kk:
			yoko += 1
			chocos = [0] * (tate + 1)
			for l in range(h):
				chocos[index[l]] += s[l][j]
			if max(chocos) > kk:
				ok = False
		if not ok:
			break
	if ok:
		ans = min(ans, tate + yoko)
print(ans)


import sys
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

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()


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

def func(div):
	ret = 0
	n_grp = len(div)
	grp = [0] * n_grp
	div.append(h)
	for c in range(w):
		for r in range(h):
			for i in range(n_grp):
				if div[i] <= r < div[i + 1]:
					grp[i] += s[r][c]
		if max(grp) > k:
			ret += 1
			grp = [0] * n_grp
			for r in range(h):
				for i in range(len(div)):
					if div[i] <= r < div[i + 1]:
						grp[i] += s[r][c]
			if max(grp) > k:
				return -1
	return ret
ans = h * w
for i in range(pow(2, h - 1)):
	div = [0]
	for j in range(h - 1):
		if i >> j & 1:
			div.append(j + 1)
	a = func(div)
	if a > -1:
		ans = min(ans, a + len(div) - 2)
print(ans)


(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):
	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)
	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
					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)


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 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, 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)):
		return True
	else:
		cutnum += 1
		lst = prelst
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)
	if noans:
		noans = 0
		continue
	else:
		ans = min(cutnum, ans)
print(ans)


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(1000000000000000.0)
	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():
	solve()

def __starting_point():
	main()
__starting_point()


(h, w, k) = map(int, input().split())
s = [list(input()) for _ in range(h)]
n = h
final = 10000000
for ii in range(2 ** (n - 1)):
	ans = 0
	op = [0] * (n - 1)
	cnt = 1
	for j in range(n - 1):
		if ii >> j & 1:
			op[j] = 1
			cnt += 1
			ans += 1
	opp = [0]
	for i in range(n - 1):
		opp.append(opp[-1] + op[i])
	h_block = [0] * cnt
	for j in range(w):
		err = False
		tmp = [0] * cnt
		for i in range(h):
			if s[i][j] == '1':
				tmp[opp[i]] += 1
		if max(tmp) > k:
			err = True
			break
		if any((tmp[i] + h_block[i] > k for i in range(cnt))):
			ans += 1
			h_block = tmp[:]
		else:
			for i in range(cnt):
				h_block[i] += tmp[i]
	if err:
		continue
	final = min(final, ans)
print(final)


from itertools import product
(H, W, K) = map(int, input().split())
grid = ''
for _ in range(H):
	grid += input()
ans = 10000
for Hcut in product((0, 1), repeat=H - 1):
	Gr_num = sum(Hcut) + 1
	old = [0] * Gr_num
	cnt = 0
	for i in range(W):
		choco = grid[i::W]
		new = [0] * Gr_num
		gr = 0
		for j in range(H):
			new[gr] += int(choco[j])
			if j < H - 1:
				if Hcut[j] == 1:
					gr += 1
		if max(new) > K:
			cnt += 10000
			break
		check = [old[gr] + new[gr] for gr in range(Gr_num)]
		if max(check) > K:
			old = new[:]
			cnt += 1
		else:
			old = check[:]
	ans = min(ans, cnt + sum(Hcut))
print(ans)


(H, W, K) = map(int, input().split())
X = [list(input()) for _ in range(H)]
MOD = 10 ** 9 + 7
ans = MOD
for bit in range(2 ** (H - 1)):
	n = bin(bit).count('1')
	ctr = [0] * (n + 1)
	res = 0
	for j in range(W):
		k = 0
		tmp = [0] * (n + 1)
		for i in range(H):
			tmp[k] += int(X[i][j])
			if bit >> i & 1:
				k += 1
		if any((v > K for v in tmp)):
			res = MOD
			break
		elif any((u + v > K for (u, v) in zip(ctr, tmp))):
			res += 1
			ctr = tmp[:]
		else:
			for i in range(n + 1):
				ctr[i] += tmp[i]
	ans = min(ans, res + n)
print(ans)


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)
ans = 100100100
for i in range(tdiv):
	lis = []
	tmp = [s[0][ii] for ii in range(w)]
	cnt = 0
	for j in range(h - 1):
		if i >> j & 1:
			tmp = [tmp[ii] + s[j + 1][ii] for ii in range(w)]
		else:
			lis.append(tmp)
			tmp = [s[j + 1][ii] for ii in range(w)]
			cnt += 1
	lis.append(tmp)
	clis = [0 for ii in range(cnt + 1)]
	tmpcnt = cnt
	for ind in range(w):
		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 max(clis) > k:
			clis = [lis[ii][ind] for ii in range(tmpcnt + 1)]
			cnt += 1
	ans = min(ans, cnt)
print(ans)


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

def calc(L):
	M = len(L)
	cnt = [0] * M
	ret = 0
	for w in range(W):
		for (i, (t, b)) in enumerate(zip(L, L[1:])):
			for j in range(t, b):
				if S[j][w] == '1':
					cnt[i] += 1
		if max(cnt) > K:
			cnt = [0] * M
			ret += 1
			for (i, (t, b)) in enumerate(zip(L, L[1:])):
				for j in range(t, b):
					if S[j][w] == '1':
						cnt[i] += 1
		if max(cnt) > K:
			return 10 ** 18
	return ret
ans = 10 ** 18
for mask in range(1 << H - 1):
	L = [0] + [d + 1 for d in range(H - 1) if mask & 1 << d > 0] + [H]
	ans = min(ans, len(L) - 2 + calc(L))
print(ans)


(h, w, k) = map(int, input().split())
s = [list(map(int, input())) for _ in range(h)]
ans = (h - 1) * (w - 1)
for bitseed in range(2 ** (h - 1)):
	i2cell = [0]
	accum_temp = 0
	for _ in range(h - 1):
		accum_temp += bitseed % 2
		i2cell.append(accum_temp)
		bitseed //= 2
	cell2whitenum = [0] * (accum_temp + 1)
	v_cut_num = 0
	for j in range(w):
		for i in range(h):
			cell2whitenum[i2cell[i]] += s[i][j]
		if max(cell2whitenum) > k:
			v_cut_num += 1
			cell2whitenum = [0] * (accum_temp + 1)
			for i in range(h):
				cell2whitenum[i2cell[i]] += s[i][j]
			if max(cell2whitenum) > k:
				v_cut_num = (h - 1) * (w - 1)
	if accum_temp + v_cut_num < ans:
		ans = accum_temp + v_cut_num
print(ans)


(h, w, k) = map(int, input().split())
S = []
for i in range(h):
	s = int(input(), 2)
	S.append(s)
ans = h + w - 2
for i in range(2 ** (h - 1)):
	flag = False
	now = 0
	cnt = 0
	y = 0
	for j in range(h - 1):
		if i >> j & 1:
			y += 1
	C = [0] * (y + 1)
	for x in range(w):
		T = []
		for j in range(h):
			cnt += S[j] >> x & 1
			if cnt > k:
				flag = True
				break
			if i >> j & 1:
				T.append(cnt)
				cnt = 0
			if j == h - 1:
				T.append(cnt)
				cnt = 0
		if flag:
			break
		for j in range(len(C)):
			if C[j] + T[j] > k:
				now += 1
				C = T
				break
			else:
				C[j] += T[j]
	if flag:
		continue
	ans = min(ans, now + y)
print(ans)


(h, w, k) = map(int, input().split())
s = [input() for i in range(h)]
ret = 10 ** 18
for bit_state in range(1 << h - 1):
	memo = {}
	pos = 0
	res = 0
	for i in range(h - 1):
		memo[i] = pos
		if bit_state & 1 << i:
			pos += 1
	memo[h - 1] = pos
	len_m = pos + 1
	ans = [0] * len_m
	flag = False
	for j in range(w):
		tmp = [0] * len_m
		for i in range(h):
			if s[i][j] == '1':
				tmp[memo[i]] += 1
		for i in range(len_m):
			if tmp[i] > k:
				flag = True
		for i in range(len_m):
			if tmp[i] + ans[i] > k:
				res += 1
				for i in range(len_m):
					ans[i] = tmp[i]
				break
		else:
			for i in range(len_m):
				ans[i] += tmp[i]
	if not flag:
		ret = min(ret, res + len_m - 1)
print(ret)


import copy
(H, W, K) = map(int, input().split())
S = [list(input()) for _ in range(H)]
ans = 10 ** 18
for i in range(1 << H - 1):
	x = bin(i).count('1')
	cho = [0] * (x + 1)
	f = 1
	cnt = x
	for w in range(W):
		j = 0
		nx = [0] * (x + 1)
		for h in range(H):
			cho[j] += int(S[h][w])
			nx[j] += int(S[h][w])
			if cho[j] > K:
				if nx[j] > K:
					f = 0
					break
				else:
					cho = copy.copy(nx)
					cnt += 1
			if i >> h & 1:
				j += 1
		if f == 0:
			break
	if f:
		ans = min(ans, cnt)
print(ans)


(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)


import sys

def main():
	input = sys.stdin.readline
	(H, W, K) = map(int, input().split())
	oS = [list(map(int, list(input().rstrip()))) for _ in range(H)]
	ans = 10 ** 10
	for p in range(1 << H - 1):
		S = [[oS[i][j] for j in range(W)] for i in range(H)]
		tmp = 0
		flag = False
		for i in range(1, H):
			if p & 1:
				for j in range(W):
					S[i][j] += S[i - 1][j]
					if S[i][j] > K:
						flag = True
			else:
				tmp += 1
			p >>= 1
		if flag:
			continue
		for j in range(W - 1):
			for i in range(H):
				if S[i][j] + S[i][j + 1] > K:
					tmp += 1
					break
			else:
				for i in range(H):
					S[i][j + 1] += S[i][j]
		ans = min(ans, tmp)
	print(ans)
main()


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

def check(Bss):
	L = len(Bss)
	accBs = [0] * L
	numCut = 0
	for i in range(W):
		for j in range(L):
			if Bss[j][i] > K:
				return H * W
			if accBs[j] + Bss[j][i] > K:
				accBs = [0] * L
				numCut += 1
				break
		for j in range(L):
			accBs[j] += Bss[j][i]
	return numCut
ans = H * W
for ptn in range(2 ** (H - 1)):
	Bss = []
	Bs = Ass[0]
	numCut = 0
	for i in range(1, H):
		if ptn >> i - 1 & 1:
			Bss.append(Bs)
			Bs = Ass[i]
			numCut += 1
		else:
			Bs = [B + A for (B, A) in zip(Bs, Ass[i])]
	Bss.append(Bs)
	numCut += check(Bss)
	ans = min(ans, numCut)
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
	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()


(h, w, k) = map(int, input().split())
ma = []
for i in range(h):
	ma.append(list(map(int, list(input()))))
ans = [0] * 2 ** (h - 1)
for i in range(2 ** (h - 1)):
	idx = [0] * h
	group = 0
	for j in range(h):
		idx[j] = group
		if i >> j & 1:
			group += 1
	ans[i] += idx[-1]
	n = idx[-1] + 1
	cnt = [0] * n
	div_w = 0
	for e in range(w):
		temp = [0] * n
		for j in range(h):
			p = idx[j]
			cnt[p] += ma[j][e]
			temp[p] += ma[j][e]
		if max(cnt) > k:
			div_w += 1
			cnt = temp
		if max(temp) > k:
			div_w = 10 ** 9
			break
	ans[i] += div_w
print(min(ans))


(H, W, K) = map(int, input().split())
S = [input() for i in range(H)]
ans = H + W
for b in range(1 << H - 1):
	gs = [[0]]
	for k in range(H - 1):
		if b & 1 << k:
			gs.append([k + 1])
		else:
			gs[-1].append(k + 1)
	tmp = bin(b).count('1')
	ws = [0] * len(gs)
	for x in range(W):
		for (i, g) in enumerate(gs):
			for h in g:
				if S[h][x] == '1':
					ws[i] += 1
		if any((w > K for w in ws)):
			tmp += 1
			ws = [0] * len(gs)
			for (i, g) in enumerate(gs):
				for h in g:
					if S[h][x] == '1':
						ws[i] += 1
			if any((w > K for w in ws)):
				tmp = H + W
				break
	ans = min(ans, tmp)
print(ans)


(H, W, K) = map(int, input().split())
S = [[int(s) for s in input()] for i in range(H)]
ans = 1000000
for i in range(2 ** (H - 1)):
	tmp = 0
	L = []
	for j in range(H - 1):
		if i >> j & 1:
			L.append(j)
	tmp += len(L)
	L.append(H - 1)
	c = [0] * len(L)
	for k in range(W):
		h = 0
		c1 = [0] * len(L)
		for l in range(len(L)):
			for m in range(h, L[l] + 1):
				c1[l] += S[m][k]
			h = L[l] + 1
		p = 0
		for l in range(len(L)):
			if c1[l] > K:
				p = 2
				break
			elif c[l] + c1[l] > K:
				p = 1
			else:
				c[l] += c1[l]
		if p == 2:
			break
		elif p == 1:
			c = [i for i in c1]
			tmp += 1
	else:
		ans = min(ans, tmp)
print(ans)


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


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
				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)
__starting_point()


from itertools import accumulate
(h, w, k) = map(int, input().split())
s = [[0] * (w + 1)] + [[0] + [int(i) for i in input()] for _ in range(h)]
for i in range(h + 1):
	s[i] = list(accumulate(s[i]))
for j in range(w + 1):
	for i in range(h):
		s[i + 1][j] += s[i][j]
ans = 10 ** 18
for i in range(1 << h - 1):
	a = []
	for j in range(h - 1):
		if i >> j & 1:
			a += [j + 1]
	a += [h]
	cnt = len(a) - 1
	q = 1
	for j in range(1, w + 1):
		p = 0
		flag = 0
		for l in a:
			if s[l][j] - s[l][j - 1] - s[p][j] + s[p][j - 1] > k:
				flag = 1
			elif s[l][j] - s[l][q - 1] - s[p][j] + s[p][q - 1] > k:
				q = j
				cnt += 1
				break
			else:
				p = l
		if flag:
			break
	else:
		ans = min(cnt, ans)
print(ans)


import itertools
INF = 10 ** 5
(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) = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(h)]
ans = float('inf')
for i in range(2 ** (h - 1)):
	L = [0]
	cnt = 0
	for j in range(h - 1):
		if i >> j & 1:
			L.append(j + 1)
			cnt += 1
	L.append(h)
	C = [0] * (len(L) - 1)
	for j in range(w):
		D = [0] * (len(L) - 1)
		for l in range(len(L) - 1):
			(a, b) = (L[l], L[l + 1])
			for s in range(a, b):
				D[l] += S[s][j]
		if max(D) > k:
			break
		for (l, d) in enumerate(D):
			if C[l] + d > k:
				break
		else:
			for (l, d) in enumerate(D):
				C[l] += d
			continue
		cnt += 1
		for (l, d) in enumerate(D):
			C[l] = d
	else:
		ans = min(ans, cnt)
print(ans)


(H, W, K) = map(int, input().split())
S = [list(input()) for _ in range(H)]
res = float('inf')
for i in range(2 ** (H - 1)):
	c = bin(i).count('1')
	cnt = c
	sum_l = [0] * (c + 1)
	j = 0
	flag = True
	while j < W:
		tmp = sum_l.copy()
		pos = 0
		for k in range(H):
			if S[k][j] == '1':
				tmp[pos] += 1
			if i >> k & 1:
				pos += 1
		if max(tmp) <= K:
			sum_l = tmp.copy()
			j += 1
			flag = False
		else:
			if flag:
				cnt = float('inf')
				break
			cnt += 1
			flag = True
			sum_l = [0] * (c + 1)
	res = min(res, cnt)
print(res)


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))
	ans = 10 ** 9
	for bit in range(1 << h - 1):
		k = 1
		tmp = 0
		while k < w:
			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)
				i = j
			else:
				k = l
				if k <= w:
					tmp += 1
				continue
			break
		else:
			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) = map(int, input().split())
s = []
INF = H - 1 + (W - 1)
ans = INF

def add(col: int):
	for i in range(g):
		now[i] += c[i][col]
	for i in range(g):
		if now[i] > K:
			return False
	return True
for _ in range(H):
	s.append(list(input()))
for div in range(1 << H - 1):
	g = 0
	id = [0] * H
	for i in range(H):
		id[i] = g
		if div >> i & 1:
			g += 1
	g += 1
	now = [0] * g
	num = g - 1
	c = [[0 for _ in range(W)] for _ in range(H)]
	for i in range(H):
		for j in range(W):
			c[id[i]][j] += int(s[i][j])
	for j in range(W):
		if not add(j):
			num += 1
			now = [0] * g
			if not add(j):
				num = INF
				break
	ans = min(ans, num)
print(ans)


from itertools import product
INFTY = 10 ** 4
(H, W, K) = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(H)]
cmin = INFTY
for x in product((0, 1), repeat=H - 1):
	cur = 0
	cnt = 0
	h = sum(x) + 1
	A = [0 for _ in range(h)]
	for j in range(W):
		ind = 0
		A0 = [0 for _ in range(h)]
		for i in range(H):
			if i < H - 1 and x[i] == 1:
				A0[ind] += S[i][j]
				ind += 1
			else:
				A0[ind] += S[i][j]
		B = [A[i] + A0[i] for i in range(h)]
		if max(A0) > K:
			cnt = INFTY
			break
		if max(B) > K:
			cur = j
			cnt += 1
			A = A0[:]
		else:
			A = B[:]
	cmin = min(cmin, cnt + sum(x))
print(cmin)


from itertools import *
(H, W, K) = 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(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)


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])
	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(Ans)
	return 0

def __starting_point():
	solve()
__starting_point()


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)


(h, w, k) = map(int, input().split())
S = [[int(i) for i in input()] for _ in range(h)]
res = 10 ** 4
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 = 10 ** 4
			break
	res = min(res, ret)
print(res)


(h, w, k) = map(int, input().split())
s = [input() for _ in range(h)]
INF = 10 ** 20
ans = INF
for div in range(1 << h - 1):
	id = []
	g = 0
	for i in range(h):
		id.append(g)
		if div >> i & 1:
			g += 1
	g += 1
	c = [[0 for _ in range(w)] for _ in range(g)]
	for i in range(h):
		for j in range(w):
			c[id[i]][j] += s[i][j] == '1'
	if max([max(l) for l in c]) > k:
		continue
	tmp_ans = g - 1
	now = [0] * g
	for j in range(w):
		for i in range(g):
			now[i] += c[i][j]
			if now[i] > k:
				tmp_ans += 1
				now = [c[gi][j] for gi in range(g)]
				break
	ans = min(ans, tmp_ans)
print(ans)


import sys
import math
import collections
import bisect
import itertools
import fractions
import copy
import decimal
import queue
sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
ni = lambda : int(sys.stdin.readline())
ns = lambda : list(map(int, sys.stdin.readline().split()))
na = lambda : list(map(int, sys.stdin.readline().split()))

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()


(H, W, K) = map(int, input().split())
choco = [list(map(int, list(input().strip()))) for i in range(H)]
ans = (H - 1) * (W - 1)
for i in range(2 ** (H - 1)):
	cut = 0
	yoko = [choco[0]]
	for j in range(H - 1):
		if i >> j & 1 == 1:
			cut += 1
			yoko.append(choco[j + 1])
		else:
			yoko[-1] = [a + b for (a, b) in zip(yoko[-1], choco[j + 1])]
	count = [yoko[i][0] for i in range(cut + 1)]
	if max(count) > K:
		continue
	for x in range(1, W):
		now_count = [yoko[y][x] for y in range(len(count))]
		next_count = [a + b for (a, b) in zip(now_count, count)]
		if max(next_count) > K:
			count = now_count
			cut += 1
		else:
			count = next_count
	ans = min(ans, cut)
print(ans)


(h, w, kk) = map(int, input().split())
G = [[0] * w for i in range(h)]
for i in range(h):
	G[i] = list(input())
for i in range(h):
	for j in range(w):
		G[i][j] = int(G[i][j])
ans = 10 ** 5
for i in range(2 ** (h - 1)):
	s = format(i, '12b')
	A = [-1]
	for j in range(h - 1):
		if s[-1 - j] == '1':
			A.append(j)
	A.append(h - 1)
	ans1 = len(A) - 2
	B = [0] * (len(A) - 1)
	c = 0
	i = 0
	while i < w:
		j = 0
		while j < len(A) - 1:
			for k in range(A[j] + 1, A[j + 1] + 1):
				B[j] += G[k][i]
			if B[j] > kk:
				c = c + 1
				B = [0] * (len(A) - 1)
				j = 0
				if c > 1010:
					j = 100
					i = 10000
			else:
				j = j + 1
		i = i + 1
	if ans1 + c < ans:
		ans = ans1 + c
print(ans)


from collections import deque
(H, W, K) = map(int, input().split())
mp = [input() for _ in range(H)]
rlt = 1010
h = deque([[1]])
while h:
	t = h.pop()
	if len(t) == H:
		t.append(1)
		tmp = sum(t) - 2
		bs = tmp
		lst = [0] * H
		j = -1
		for i in range(len(t) - 1):
			if t[i] == 1:
				j += 1
			lst[i] = j
		cnt = [0] * (lst[-1] + 1)
		for j in range(W):
			tcnt = [0] * (lst[-1] + 1)
			f = 0
			for i in range(H):
				tcnt[lst[i]] += int(mp[i][j])
			for k in range(lst[-1] + 1):
				if tcnt[k] > K:
					f = 2
					break
				cnt[k] += tcnt[k]
				if cnt[k] > K:
					f = 1
					break
			if f == 2:
				break
			if f == 1:
				tmp += 1
				for k in range(lst[-1] + 1):
					cnt[k] = tcnt[k]
		if f < 2:
			rlt = min(rlt, tmp)
	else:
		for i in range(2):
			h.append(t + [i])
print(rlt)


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)
count = H - 1 + (W - 1)
for k in range(H):
	if count <= k:
		break
	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]
			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)


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

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
ans = 10 ** 30
for i in range(2 ** (H - 1)):
	g = 0
	id = [-1] * H
	for j in range(H):
		id[j] = g
		if i >> j & 1:
			g += 1
	g += 1
	c = [[0] * W for _ in range(H)]
	for i in range(H):
		for j in range(W):
			c[id[i]][j] += S[i][j]
	num = g - 1
	now = [0] * g
	for j in range(W):
		if not add(j):
			num += 1
			now = [0] * g
			if not add(j):
				num = 10 ** 30
				continue
	ans = min(ans, num)
print(ans)


(h, w, K) = map(int, input().split())
s = []
for i in range(h):
	s.append(input())
ans = float('inf')
for i in range(2 ** (h - 1)):
	cut = []
	linecount = 0
	for j in range(h - 1):
		if (i >> j) % 2 == 1:
			cut.append(j)
	counter = [0] * (len(cut) + 1)
	for j in range(w):
		ncounter = [0] * (len(cut) + 1)
		area = 0
		flag = False
		for k in range(h):
			ncounter[area] += int(s[k][j])
			if counter[area] + ncounter[area] > K:
				if ncounter[area] > K:
					linecount = float('inf')
				flag = True
			if k in cut:
				area += 1
		if flag:
			counter = ncounter[:]
			linecount += 1
		else:
			for l in range(len(cut) + 1):
				counter[l] += ncounter[l]
	ans = min(ans, linecount + len(cut))
print(ans)


def f(nums, K, w):
	h = len(nums)
	counter = [nums[x][0] for x in range(h)]
	if max(counter) > K:
		return float('inf')
	out = 0
	for i in range(1, w):
		for x in range(h):
			counter[x] += nums[x][i]
		if max(counter) > K:
			out += 1
			counter = [nums[x][i] for x in range(h)]
	return out
(H, W, K) = map(int, input().split())
S = [input() for _ in range(H)]
S = [[int(S[i][j]) for j in range(W)] for i in range(H)]
ans = float('inf')
for p in range(2 ** (H - 1)):
	q = '0' + format(p, '0' + str(H - 1) + 'b') + '1'
	i = 0
	c = 0
	nums = []
	while i < H:
		j = 1
		while i + j < H and q[i + j] == '0':
			j += 1
		tmp = S[i:i + j]
		nums.append([sum([tmp[y][x] for y in range(j)]) for x in range(W)])
		i += j
	cand = f(nums, K, W) + q.count('1') - 1
	if ans > cand:
		ans = cand
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)):
	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):
		if h_cut & 2 ** (-i + h - 1):
			idx += 1
		temp_dict[i] = idx
	iw = 0
	while iw < w:
		for ih in range(h):
			temp_list[temp_dict[ih]] += choco[ih][iw]
		condition = max(temp_list) > k
		if condition:
			if w_last_cot_pos < iw - 1:
				num_cut += 1
				w_last_cot_pos = iw - 1
				temp_list = [0] * (num_cut_init + 1)
			else:
				valid = False
				break
		else:
			iw += 1
	if valid:
		ans = min(ans, num_cut)
print(ans)


(H, W, K) = map(int, input().split())
S = [list(map(int, input())) for _ in range(H)]
ans = float('inf')
for i in range(1 << H - 1):
	data = [S[0][0:]]
	for j in range(H - 1):
		if i >> j & 1:
			data.append([0] * W)
		for k in range(W):
			data[-1][k] += S[j + 1][k]
	if any([any([x > K for x in y]) for y in data]):
		continue
	cnt = len(data) - 1
	judge = [0] * len(data)
	for j in range(W):
		if any([judge[x] + data[x][j] > K for x in range(len(data))]):
			judge = [0] * len(data)
			cnt += 1
		judge = [judge[x] + data[x][j] for x in range(len(data))]
	ans = min(ans, cnt)
print(ans)


import itertools
inpl = lambda : list(map(int, input().split()))
(H, W, K) = inpl()
S = [input() for h in range(H)]
ans = H + W
for c in itertools.product(range(2), repeat=H - 1):
	hcut = sum(c)
	if hcut >= ans:
		continue
	segment = [0]
	s = 0
	for h in range(H - 1):
		if c[h]:
			s += 1
		segment.append(s)
	cur = hcut
	whites = [0] * (hcut + 1)
	for w in range(W):
		thisline = [0] * (hcut + 1)
		for h in range(H):
			if S[h][w] == '1':
				whites[segment[h]] += 1
				thisline[segment[h]] += 1
		m = max(whites)
		if m > K:
			whites = thisline
			m = max(whites)
			cur += 1
			if cur >= ans or m > K:
				break
	else:
		ans = cur
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)


(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
	for j in range(w):
		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
				break
		f = 0
	if mc > cc + len(set(i)) - 1:
		mc = cc + len(set(i)) - 1
print(mc)


from itertools import product, accumulate
(H, W, K) = map(int, input().split())
grid = tuple((tuple(map(int, input())) for _ in range(H)))

def check(gids):
	cnt = 0
	s = [0] * (gids[-1] + 1)
	for i in range(W):
		for (h, gid) in enumerate(gids):
			s[gid] += grid[h][i]
		if any((v > K for v in s)):
			cnt += 1
			s = [0] * (gids[-1] + 1)
			for (h, gid) in enumerate(gids):
				s[gid] += grid[h][i]
			if any((v > K for v in s)):
				return float('inf')
	return cnt

def it():
	for p in product(range(2), repeat=H - 1):
		gids = [0] + list(accumulate(p))
		yield (check(gids) + gids[-1])
print(min(it()))


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())


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()


import copy
(h, w, k) = map(int, input().split())
s = []
for i in range(h):
	s += [[int(i) for i in input()]]
ans = h + w - 2
for i in range(2 ** (h - 1)):
	t = format(i, ''.join(['0', str(h - 1), 'b']))
	a = sum([int(tt) for tt in t])
	h1 = [0] + [ii + 1 for ii in range(h - 1) if t[ii] == '1'] + [h]
	h2 = [[h1[ii], h1[ii + 1]] for ii in range(len(h1) - 1)]
	j0 = 0
	slsum = [0] * len(h2)
	sl = [0] * len(h2)
	for j in range(w):
		for l in range(len(h2)):
			sl[l] = sum([s[ii][j] for ii in range(h2[l][0], h2[l][1])])
			slsum[l] += sl[l]
			if sl[l] > k:
				a = -1
				break
		if a == -1:
			break
		if any([x > k for x in slsum]):
			slsum = copy.deepcopy(sl)
			a += 1
	if a == -1:
		continue
	ans = min(ans, a)
print(ans)


from itertools import accumulate
import sys
input = sys.stdin.readline
(H, W, K) = map(int, input().split())
S = [list(map(int, input().rstrip())) for _ in range(H)]
cum = [list(accumulate(S[i])) for i in range(H)]
ans = float('inf')
for bit in range(1 << H - 1):
	cnt = 0
	prev = -1
	for h in range(H - 1):
		cnt += bit >> h & 1
	for w in range(W):
		s = 0
		cut = False
		for h in range(H):
			if h > 0 and bit >> h - 1 & 1:
				if s > K:
					cut = True
					break
				s = 0
			s += cum[h][w] - (cum[h][prev] if prev >= 0 else 0)
		if s > K:
			cut = True
		if cut:
			if w - 1 == prev:
				break
			cnt += 1
			prev = w - 1
			continue
	else:
		ans = min(ans, cnt)
print(ans)


def main():
	(H, W, K) = map(int, input().split())
	g = [input() for _ in range(H)]
	ans = 1 << 100
	for i in range(1 << H - 1):
		need = bin(i).count('1')
		sz = need + 1
		cnt = [0] * sz
		f = 1
		for j in range(W):
			c = 0
			for k in range(H):
				cnt[c] += g[k][j] == '1'
				if cnt[c] > K:
					break
				c += i >> k & 1
			else:
				continue
			cnt = [0] * sz
			need += 1
			if need > ans:
				f = 0
				break
			c = 0
			for k in range(H):
				cnt[c] += g[k][j] == '1'
				if cnt[c] > K:
					break
				c += i >> k & 1
			else:
				continue
			f = 0
			break
		if f:
			ans = min(ans, need)
	print(ans)
main()


(h, *s) = open(0)
(h, w, k, *m) = map(int, h.split())
b = 512
while b:
	b -= 1
	r = t = j = 0
	d = [0] * h
	while w - j:
		i = c = 0
		while h - i:
			d[c] += s[i][j] > '0'
			f = d[c] > k
			if (t < j) & f:
				r += 1
				t = j
				d = [0] * h
				break
			r += h * w * f
			c += b >> i & 1
			i += 1
		else:
			j += 1
			v = c
	m += (r + v,)
print(min(m))


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

def divide(pattern):
	lenP = len(pattern)
	divided = [0] * lenP
	count = lenP - 1
	for i in range(lenP):
		if K < pattern[i][0]:
			return H + W
	for i in range(1, W):
		for j in range(lenP):
			if K < pattern[j][i] - divided[j]:
				for l in range(lenP):
					divided[l] = pattern[l][i - 1]
				count += 1
				break
	return count
ans = H + W
for i in range(2 ** H):
	pattern = []
	line = [0] * W
	for j in range(H):
		for k in range(W):
			line[k] += S[j][k]
		if 2 ** j & i:
			pattern.append(line)
			line = [0] * W
	pattern.append(line)
	ans = min(divide(pattern), ans)
print(ans)


(H, W, K) = map(int, input().split())
chocolate = []
for _ in range(H):
	chocolate.append(list(input()))
INF = 10 ** 15
ans = INF
for div in range(1 << H - 1):
	g = 0
	id = [None] * H
	for i in range(H):
		id[i] = g
		if div >> i & 1:
			g += 1
	c = [[0] * W for _ in range(g + 1)]
	for (i, block) in zip(id, chocolate):
		for (j, b) in enumerate(block):
			if b == '1':
				c[i][j] += 1
	now = [0] * (g + 1)
	lines = g
	for j in range(W):
		for i in range(g + 1):
			now[i] += c[i][j]
		ok = all((n <= K for n in now))
		if not ok:
			lines += 1
			now = [0] * (g + 1)
			for i in range(g + 1):
				now[i] += c[i][j]
			ok = all((n <= K for n in now))
			if not ok:
				lines = INF
				break
	ans = min(ans, lines)
print(ans)


import sys
input = sys.stdin.readline

def main():
	(H, W, K) = map(int, input().split())
	mas = [input().strip('\n') for i in range(H)]
	mincut = H * W
	for bit in range(2 ** (H - 1)):
		sep = []
		for s in range(H - 1):
			if bit >> s & 1:
				sep.append(s)
		cutcnt = len(sep)
		cnt = [0] * (len(sep) + 1)
		for j in range(W):
			ci = 0
			cntt = cnt[:]
			for i in range(H):
				if mas[i][j] == '1':
					cnt[ci] += 1
				if i in sep:
					ci += 1
			if max(cnt) > K:
				for i in range(len(sep) + 1):
					cnt[i] -= cntt[i]
				cutcnt += 1
		if max(cnt) > K:
			cutcnt = 10000000000
		if cutcnt < mincut:
			mincut = cutcnt
	print(mincut)
main()


import sys
input = sys.stdin.readline
(H, W, K) = map(int, input().split())
MAP = [input().strip() for i in range(H)]
ANS = 1 << 30
for i in range(1 << H - 1):
	A = []
	for j in range(H):
		if i & 1 << j != 0:
			A.append(j + 1)
	SCORE = len(A)
	B = [0] * (len(A) + 1)
	for w in range(W):
		ind = 0
		for i in range(H):
			if ind < len(A) and i == A[ind]:
				ind += 1
			if MAP[i][w] == '1':
				B[ind] += 1
		if max(B) > K:
			SCORE += 1
			B = [0] * (len(A) + 1)
			ind = 0
			for i in range(H):
				if ind < len(A) and i == A[ind]:
					ind += 1
				if MAP[i][w] == '1':
					B[ind] += 1
		if max(B) > K:
			break
	else:
		ANS = min(ANS, SCORE)
print(ANS)


from itertools import combinations
(H, W, K) = map(int, input().split())
S = [input() for _ in range(H)]
C = [[0] * (W + 1) for _ in range(H + 1)]
for h in range(H):
	wc = 0
	for w in range(W):
		wc += S[h][w] == '1'
		C[h + 1][w + 1] = C[h][w + 1] + wc
ans = 2000
for cuth in range(H):
	for comb in combinations([h for h in range(1, H)], cuth):
		comb = [0] + list(comb) + [H]
		(wi, cutw) = (0, 0)
		for w in range(W):
			if max([C[comb[i]][w + 1] - C[comb[i]][wi] - C[comb[i - 1]][w + 1] + C[comb[i - 1]][wi] for i in range(1, len(comb))]) > K:
				if wi == w:
					cutw = 2000
				(wi, cutw) = (w, cutw + 1)
		ans = min(ans, cuth + cutw)
print(ans)


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)


(h, w, k) = map(int, input().split())
s = [input() for _ in range(h)]
ans = float('inf')
for bit in range(1 << h - 1):
	cnt = 0
	l = [0] * h
	for i in range(h - 1):
		if bit & 1 << i:
			cnt += 1
		l[i + 1] = cnt
	m = max(l) + 1
	cnt2 = m - 1
	c = [0] * m
	for j in range(w):
		cur = [0] * m
		for i in range(h):
			c[l[i]] += int(s[i][j])
			cur[l[i]] += int(s[i][j])
			if c[l[i]] > k:
				cnt2 += 1
				for i in range(m):
					c[i] = cur[i]
	ans = min(ans, cnt2)
print(ans)


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()


(H, W, K) = map(int, input().split())
m = []
for h in range(H):
	m.append(list(map(int, list(input()))))
ans = float('inf')
for hb in range(2 ** (H - 1)):
	hl = []
	for i in range(H - 1):
		if hb & 1 << i > 0:
			hl.append(i + 1)
	t = len(hl)
	hl = [0] + hl + [H]
	(w, pw) = (0, 0)
	wl = [0] * len(hl)
	while w < W:
		ok = True
		for i in range(len(hl) - 1):
			(sh, eh) = (hl[i], hl[i + 1])
			for h in range(sh, eh):
				wl[i] += m[h][w]
				if wl[i] > K:
					ok = False
					break
			if not ok:
				break
		if not ok:
			if pw == w:
				t = float('inf')
				break
			(pw, w) = (w, w)
			t += 1
			wl = [0] * len(hl)
		else:
			w += 1
	ans = min(t, ans)
print(ans)


(h, w, k) = (int(x) for x in input().split())
S = [input() for _ in range(h)]
ans = 10 ** 18
for bit in range(1 << h - 1):
	segment = [0] * h
	seg_label = 0
	for i in range(h - 1):
		if bit & 1 << i:
			seg_label += 1
		segment[i + 1] = seg_label
	n = max(segment) + 1
	count = n - 1
	k_count = [0] * n
	for j in range(w):
		tmp_count = [0] * n
		for i in range(h):
			k_count[segment[i]] += int(S[i][j])
			tmp_count[segment[i]] += int(S[i][j])
			if k_count[segment[i]] > k:
				count += 1
				for seg in range(n):
					k_count[seg] = tmp_count[seg]
	ans = min(ans, count)
print(ans)


(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) = list(map(int, input().split()))
S = [input() for _ in range(H)]
ans = 10 ** 10
for i in range(2 ** (H - 1)):
	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 math
(H, W, K) = map(int, input().split())
S = [list(map(lambda x: int(x == '1'), input())) for _ in range(H)]

def cal_min_vert_div(hs):
	cnt = 0
	n_h_div = len(hs)
	n_white = [0] * n_h_div
	for i in range(W):
		for j in range(n_h_div):
			n_white[j] += hs[j][i]
			if n_white[j] > K:
				n_white = [hs[k][i] for k in range(n_h_div)]
				cnt += 1
				if max(n_white) > K:
					return math.inf
				break
	return cnt
ans = math.inf
for mask in range(2 ** (H - 1)):
	hs = []
	tmp = S[0]
	for i in range(H - 1):
		if mask >> i & 1:
			hs.append(tmp)
			tmp = S[i + 1]
		else:
			tmp = [tmp[w] + S[i + 1][w] for w in range(W)]
	hs.append(tmp)
	tmp = cal_min_vert_div(hs) + sum(map(int, bin(mask)[2:]))
	ans = min(ans, tmp)
print(ans)


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


(H, W, K) = map(int, input().split())
S = []
ans = 10 ** 9
for i in range(H):
	S.append(input())
for div in range(1 << H - 1):
	ID = [0] * H
	g = 0
	for i in range(H):
		ID[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):
			if S[i][j] == '1':
				c[ID[i]][j] += 1
	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
			if not add(j):
				num = 10 ** 9
				break
	ans = min(ans, num)
print(ans)


(h, w, K) = map(int, input().split())
s = [input() for i in range(h)]
ans = float('inf')
for i in range(2 ** (h - 1)):
	a = format(i, 'b').zfill(h - 1)
	choco = [[int(x) for x in s[0]]]
	for k in range(1, h):
		if a[k - 1] == '1':
			choco.append([0 for x in range(w)])
		for j in range(w):
			if s[k][j] == '1':
				choco[-1][j] += 1
	b = 0
	c = [0 for x in range(len(choco))]
	ok = 1
	for j in range(w):
		for k in range(len(choco)):
			if choco[k][j] > K:
				ok = 0
				break
			c[k] += choco[k][j]
		if max(c) > K:
			b += 1
			c = [choco[x][j] for x in range(len(choco))]
	if ok:
		ans = min(b + a.count('1'), ans)
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()


(H, W, K) = map(int, input().split())
S = [input() for i in range(H)]
ans = H + W
for b in range(1 << H - 1):
	tmp = bin(b).count('1')
	ks = [0] * H
	valid = True
	for col in zip(*S):
		j = 0
		for (i, c) in enumerate(col):
			if c == '1':
				ks[j] += 1
			if b & 1 << i:
				j = i + 1
		if any((k > K for k in ks)):
			tmp += 1
			ks = [0] * H
			j = 0
			for (i, c) in enumerate(col):
				if c == '1':
					ks[j] += 1
				if b & 1 << i:
					j = i + 1
			if any((k > K for k in ks)):
				valid = False
				break
	if valid:
		ans = min(ans, tmp)
print(ans)


from itertools import combinations
(h, w, k) = map(int, input().split())
S = [list(map(int, list(input()))) for _ in range(h)]
ans = 10 ** 9
for i in range(2 ** (h - 1)):
	box = [[0] * w]
	bcnt = 0
	box[bcnt] = [s + b for (s, b) in zip(S[0], box[bcnt])]
	for j in range(1, h):
		if i >> j - 1 & 1:
			bcnt += 1
			box.append([0] * w)
		box[bcnt] = [s + b for (s, b) in zip(S[j], box[bcnt])]
	if not all([all([i <= k for i in b]) for b in box]):
		continue
	cutcnt = len(box) - 1
	cnt = [0] * len(box)
	for m in range(w):
		for n in range(len(box)):
			cnt[n] += box[n][m]
		if any([c > k for c in cnt]):
			cutcnt += 1
			for n in range(len(box)):
				cnt[n] = box[n][m]
	ans = min(ans, cutcnt)
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)


(h, w, k) = map(int, input().split())
Cho = [list(map(int, list(input()))) for _ in range(h)]
ans = 10000000
for i in range(2 ** (h - 1)):
	need = 0
	seq = []
	t = []
	for j in range(h - 1):
		t.append(j)
		if i & 1 << j:
			need += 1
			seq.append(t)
			t = []
	seq.append(t + [h - 1])
	f = 1
	q = need + 1
	cnt = [0] * q
	for x in range(w):
		cntp = [0] * q
		for (i, g) in enumerate(seq):
			cntg = 0
			for y in g:
				cntg += Cho[y][x]
				if cntg > k:
					f = 0
					break
				cntp[i] += Cho[y][x]
			if not f:
				break
		if not f:
			break
		for xx in range(q):
			cnt[xx] += cntp[xx]
		if any((xxx > k for xxx in cnt)):
			need += 1
			if need > ans:
				f = 0
				break
			cnt = cntp
	if f:
		ans = min(ans, need)
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)
	wk = 0
	for i in grid:
		if i == 1:
			wk += 1
	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)


(h, w, k) = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h * w <= k:
	result.append(0)
else:
	for i in range(2 ** (h - 1)):
		(checker, num, p) = (0, i, [0])
		for _ in range(h):
			p.append(p[-1] + num % 2)
			checker += num % 2
			num >>= 1
		x = 0
		c = [0 for _ in range(checker + 1)]
		for j in range(w):
			num = i
			nex = [0 for _ in range(checker + 1)]
			for m in range(h):
				nex[p[m]] += s[m][j]
			if max(nex) > k:
				x = float('inf')
				break
			for m in range(checker + 1):
				c[m] += nex[m]
				if c[m] > k:
					c = nex
					x += 1
					break
		result.append(checker + x)
print(min(result))


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


(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 (idx, cond) in enumerate(product((True, False), repeat=h - 1)):
	div = sum(cond)
	spl = [arr[0][:]]
	for i in range(h - 1):
		if cond[i]:
			spl.append(arr[i + 1][:])
		else:
			spl[-1] = [spl[-1][j] + arr[i + 1][j] for j in range(w)]
	num = len(spl)
	cnt = [0] * num
	for v in range(w):
		tmp = [spl[i][v] for i in range(num)]
		if max(tmp) > k:
			break
		if max([cnt[i] + tmp[i] for i in range(num)]) > k:
			div += 1
			cnt = tmp[:]
		else:
			cnt = [cnt[i] + tmp[i] for i in range(num)]
	else:
		ans = min(ans, div)
print(ans)


import sys
input = sys.stdin.readline
(h, w, k) = map(int, input().split())
l = [None] * h
for i in range(h):
	l[i] = list(input())
from itertools import *
ans = 10 ** 10
import copy
for tmp in list(product([True, False], repeat=h - 1)):
	num_sp = sum(tmp) + 1
	cnt = [0] * num_sp
	nxt_cnt = [0] * num_sp
	last_spl = -1
	ok = True
	spl_l = []
	for aaa in range(h):
		spl_l.append(sum(tmp[:aaa]))
	cur_ans = sum(tmp)
	for i in range(w):
		for j in range(h):
			spl = spl_l[j]
			nxt_cnt[spl] += int(l[j][i])
			cnt[spl] += int(l[j][i])
		if max(cnt) > k:
			cur_ans += 1
			cnt = copy.copy(nxt_cnt)
			if last_spl + 1 == i or max(nxt_cnt) > k:
				ok = False
				break
			last_spl = i - 1
		nxt_cnt = [0] * num_sp
		if not ok:
			break
	if ok:
		ans = min(ans, cur_ans)
print(ans)


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
			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()


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
	if succ:
		ans = min(ans, cnt)
print(ans)


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()


(H, W, K) = map(int, input().split())
S = [list(map(int, input())) for _ in [0] * H]
ans = H * W
S2 = [[0] * (W + 1) for _ in [0] * (H + 1)]
for i in range(H):
	for j in range(W):
		S2[i + 1][j + 1] = S2[i][j + 1] + S[i][j]
for i in range(1, H + 1):
	for j in range(W):
		S2[i][j + 1] += S2[i][j]
for i in range(1 << H - 1):
	check = [0] + [j + 1 for j in range(H - 1) if i >> j & 1] + [H]
	cnt = len(check) - 2
	l = 0
	r = 1
	while r <= W:
		for (j, k) in zip(check[:-1], check[1:]):
			if S2[j][l] + S2[k][r] - S2[j][r] - S2[k][l] > K:
				if r == l + 1:
					cnt += H * W
					r = W + 1
					break
				cnt += 1
				l = r - 1
				r = r
				break
		else:
			r += 1
	ans = min(ans, cnt)
print(ans)


sel = 'E'
if sel == 'A':
	(N, M) = list(map(int, input().split()))
	ans = 0
	ans += M * (M - 1) // 2
	ans += N * (N - 1) // 2
	print(ans)
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')
if sel == 'C':
	L = int(input())
	print(L ** 3 / 27)
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)
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)


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()


(h, w, k) = map(int, input().split())
S = [[int(s) for s in list(input())] for i in range(h)]
ans = 10 ** 4
for b in range(2 ** (h - 1)):
	cnt = bin(b).count('1')
	B = format(b, 'b').zfill(h - 1) + '1'
	T = [[0] * w for i in range(cnt + 1)]
	for j in range(w):
		(t, c) = (0, 0)
		for i in range(h):
			t += S[i][j]
			if B[i] == '1':
				T[c][j] += t
				t = 0
				c += 1
	if max([max(T[i]) for i in range(cnt + 1)]) > k:
		continue
	A = [T[i][0] for i in range(cnt + 1)]
	tmp = cnt
	for j in range(1, w):
		A = [A[i] + T[i][j] for i in range(cnt + 1)]
		if any([a > k for a in A]):
			A = [T[i][j] for i in range(cnt + 1)]
			tmp += 1
	ans = min(ans, tmp)
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
(h, w, k) = map(int, input().split())
S = [input() for _ in range(h)]
ans = float('inf')
import bisect
for i in range(2 ** (h - 1)):
	Cut = []
	cur = 0
	for ii in range(h - 1):
		if i & 1 << ii:
			Cut.append(ii)
	p = len(Cut) + 1
	Num = [0] * h
	for ii in range(h):
		Num[ii] = bisect.bisect_left(Cut, ii)
	A = [0] * p
	Chk = True
	for j in range(w):
		B = [0] * p
		for jj in range(h):
			if S[jj][j] == '1':
				B[Num[jj]] += 1
		for jj in range(p):
			if B[jj] > k:
				Chk = False
			if A[jj] + B[jj] > k:
				cur += 1
				A = B
				break
			else:
				continue
		else:
			for jjj in range(p):
				A[jjj] += B[jjj]
	if Chk:
		ans = min(ans, cur + p - 1)
print(ans)


(h, w, k) = map(int, input().split())
s = [list(map(int, input())) for i in range(h)]
ans = h + w - 2
for i in range(2 ** (h - 1)):
	index = [0] * h
	rowcuts = 0
	for j in range(h - 1):
		if 1 & i >> j == 1:
			rowcuts += 1
		index[j + 1] = rowcuts
	chocos = [0] * (rowcuts + 1)
	coulmncuts = 0
	valid = True
	for j in range(w):
		for l in range(h):
			chocos[index[l]] += s[l][j]
		if max(chocos) > k:
			coulmncuts += 1
			chocos = [0] * (rowcuts + 1)
			for l in range(h):
				chocos[index[l]] += s[l][j]
			if max(chocos) > k:
				valid = False
		if not valid:
			break
	if valid:
		ans = min(ans, rowcuts + coulmncuts)
print(ans)


import sys
sys.setrecursionlimit(10000)
(H, W, K) = map(int, input().split())
S = [input() for _ in range(H)]
ans = 10000

def check(border, num):
	global H, W, K, S
	now = [0] * (num + 1)
	add = 0
	for j in range(W):
		tmp = [0] * (num + 1)
		for i in range(H):
			now[border[i]] += int(S[i][j])
			tmp[border[i]] += int(S[i][j])
		if max(now) > K:
			add += 1
			now = tmp
		if max(tmp) > K:
			return 10000
	return num + add

def rec(border, num, i):
	global H, W, K, S, ans
	if i < H:
		border[i] = num
		rec(border, num, i + 1)
		border[i] = num + 1
		rec(border, num + 1, i + 1)
	else:
		ans = min(ans, check(border, num))
rec([0] * H, 0, 1)
print(ans)