Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import collections
import sys

*data, = map(int, sys.stdin.read().split()[::-1])

def inp():
    return data.pop()

h, w, m = inp(), inp(), inp()


targets = set()
xs = []
ys = []
for _ in range(m):
    y, x = inp(), inp()
    # y -= 1
    # x -= 1
    ys.append(y)
    xs.append(x)
    targets.add((y, x))

x_stat = collections.Counter(xs)
y_stat = collections.Counter(ys)

xs = sorted(set(xs), key=lambda obj: x_stat[obj], reverse=True)
ys = sorted(set(ys), key=lambda obj: y_stat[obj], reverse=True)

mx_x = x_stat[xs[0]]
mx_y = y_stat[ys[0]]
while xs and x_stat[xs[-1]] < x_stat[xs[0]]:
    xs.pop()
while ys and y_stat[ys[-1]] < y_stat[ys[0]]:
    ys.pop()
best_res = 0
# print(xs, x_stat)
# print(ys, y_stat)
for x in xs:
    for y in ys:
        cur = x_stat[x] + y_stat[y] - ((y, x) in targets)
        best_res = max(cur, best_res)
print(best_res)





### FIXED CODE ###

import collections
import sys

*data, = map(int, sys.stdin.read().split()[::-1])

def inp():
    return data.pop()

h, w, m = inp(), inp(), inp()


targets = set()
xs = []
ys = []
for _ in range(m):
    y, x = inp(), inp()
    # y -= 1
    # x -= 1
    ys.append(y)
    xs.append(x)
    targets.add((y, x))

x_stat = collections.Counter(xs)
y_stat = collections.Counter(ys)

xs = sorted(set(xs), key=lambda obj: x_stat[obj], reverse=True)
ys = sorted(set(ys), key=lambda obj: y_stat[obj], reverse=True)

mx_x = x_stat[xs[0]]
mx_y = y_stat[ys[0]]
while xs and x_stat[xs[-1]] < x_stat[xs[0]]:
    xs.pop()
while ys and y_stat[ys[-1]] < y_stat[ys[0]]:
    ys.pop()
# print(xs, x_stat)
# print(ys, y_stat)

found = False
for x in xs:
    for y in ys:
        if (y, x) not in targets:
            found = True
            break
ans = mx_y + mx_x
if not found:
    ans -= 1
print(ans)
### BUGGY CODE ###

n=int(input())
d=list(map(int,input().split()))
cnt=0
for i in range(min(d),max(d)+1):
    abc=0
    arc=0
    for j in range(len(d)):
        if d[j] <= i:
            abc+=1
        else:
            arc+=1
    if abc == arc:
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
A=sorted(d)
print(A[len(d)//2]-A[(len(d)//2)-1])
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, m = LI()
total = m * 3


fac = [1] * (total + n)
inv = [1] * (total + n)
i = 1
for j in range(1, total + n):
    i = i * j % mod
    fac[j] = i
    inv[j] = pow(i, mod - 2, mod)



def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod



impossible = 0
for i in range(m + 2, total + 1, 2):
    impossible = (impossible + comb(n, i) * comb(n + (total - i) // 2 - 1, n - 1) % mod) % mod


ret = 0
for i in range(m):
    ret = (ret + comb(i + n - 2, n - 2)) % mod


impossible = (impossible + ret * n) % mod


ret = 0
print((comb(total + n - 1, n - 1) - impossible) % mod)

### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, m = LI()
total = m * 3

fac = [1] * (total+n+1)
inv = [1] * (total+n+1)
for i in range(total+n):
    fac[i+1] = fac[i]*(i+1)%mod

inv[total+n]=pow(fac[-1], mod-2, mod)
for j in range(total+n-1, -1, -1):
    inv[j]=inv[j+1]*(j+1)%mod



def comb(n, r):
    if r > n:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod


ans = comb(total+n-1, n-1)
for i in range(m + 2, min(n + 1, total + 1)):
    if (total - i) % 2 == 0:
        ans -= comb(n, i) * comb(n + (total - i) // 2 - 1, n - 1) % mod
        ans %= mod


ret = 0
for i in range(m):
    ret = (ret + comb(i + n - 2, n - 2)) % mod


ans -= (ret * n) % mod
print(ans % mod)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
S = sorted(list(set(A)), reverse=True)

L = []
for s in S:
    if A.count(s) > 3:
        L.append(s)
        L.append(s)
    elif A.count(s) > 1:
        L.append(s)
    if len(L) > 1:
        print(L[0]*L[1])
        break
else:
    print(0)


### FIXED CODE ###

import collections

n = int(input())
A = list(map(int, input().split()))
S = sorted(list(set(A)), reverse=True)
c = collections.Counter(A)

L = []
for s in S:
    if c[s] > 3:
        L.append(s)
        L.append(s)
    elif c[s] > 1:
        L.append(s)
    if len(L) > 1:
        print(L[0]*L[1])
        break
else:
    print(0)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
res = []
for i in range(n):
    s = 0
    for pm, j in enumerate(range(i, i+n)):
        s += a[j%n] * [-1, 1][pm %2 ==0]
    res.append(s)

print(' '.join(map(str, res)))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

res = []
s = 0
for i in range(n):
    s += a[i] * [-1, 1][i % 2 ==0]
res.append(s)

for i in range(1, n):
    res.append(2*a[i-1] - res[i-1])

print(' '.join(map(str, res)))
### BUGGY CODE ###

N = int(input())
A = input().split()
answer = 1
flag = 0
x = 10**18
for i in range(N):
  answer *= int(A[i])

check = answer/x
if ((check) >= 1) and (answer != x):
  print(-1)
else:
  print(answer)



### FIXED CODE ###

N = int(input())
A = input().split()
answer = 1
flag = 0
x = 10**18

if '0' in A:
  print(0)
  flag = 1
  


if flag == 0:
  for i in range(N):
    answer *= int(A[i])
    if answer > x:
      print(-1)
      flag = 1
      break

if flag == 0:    
  print(answer)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
check = 10**18
ans = a[0]

for  i in range(1,n):
    ans = ans * a[i]
if ans <= check:
    print(ans)
else:
    print('-1')


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
check = 10**18

a = sorted(a)
ans = a[0]
tmp = 0


for i in range(n-1,0,-1):
    ans = ans * a[i]
    if ans > check:
        tmp  = 1
        break
    elif a[0] == 0:
        tmp = 2
        break

if tmp == 1:
    print('-1')
elif tmp == 0:
    print(ans)
elif tmp == 2:
    print('0')
### BUGGY CODE ###

n = int(input())

def luca(n):
    if n == 0:
        return 2
    elif n ==1:
        return 1
    else:
        a = luca(n-1)
        b = luca(n-2)
        c = a+b
        return c
 
if __name__ == "__main__":
    print(luca(n))

### FIXED CODE ###

n = int(input())

def luca(n):
    a = [None] * (n+1)
    a[0] = 2
    a[1] = 1
    for i in range(2, n+1):
        a[i] = a[i-1] + a[i-2]
    return a[n]
 
if __name__ == "__main__":
    print(luca(n))
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[]
L=[]
for ix in range(x):
  for iy in range(y):
    l.append(a[ix]+b[iy])
l.sort()
l.reverse()
if len(l)>k:
  l=l[0:k]
for iz in range(z):
  for i in range(len(l)):
    L.append(c[iz]+l[i])
L.sort()
L.reverse()
for i in range(k):
  print(L[i])

### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[]
L=[]
for ix in range(x):
  for iy in range(y):
    l.append(a[ix]+b[iy])
l.sort()
l.reverse()
if len(l)>k:
  l=l[0:k]
for iz in range(z):
  for i in range(len(l)):
    L.append(c[iz]+l[i])
L.sort()
L.reverse()
for i in range(k):
  print(L[i])
### BUGGY CODE ###

N = int(input())
S = []
cnt = []
ans = []

for i in range(N):
    x = str(input())
    if x in S:
        num = S.index(x)
        cnt[num] += 1
    else:
        S.append(x)
        cnt.append(1)

for j in range(len(cnt)):
    if max(cnt) == cnt[j]:
        ans.append(S[j])

ans.sort()
for x in range(len(ans)):
    print(ans[x])


### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]
d = {}

for i in s:
    d[i] = d.get(i, 0) + 1

d = sorted(d.items(), key=lambda x: x[1], reverse=True)
maxv = d[0][1]
ans = []
for s in d:
    if s[1] == maxv:
        ans.append(s[0])
    else:
        break

for p in sorted(ans):
    print(p)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
H,W=map(int, sys.stdin.readline().split())

A=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]
B=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

dp=[ [ set() for _ in range(W) ] for __ in range(H) ]

#初期化
r,c=0,0
val=A[r][c]
dp[r][c].add(val)

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]

while q:
    r,c=q.popleft()
    for dr,dc in D:
        if r+dr<H and c+dc<W:
            next_r=r+dr
            next_c=c+dc
            next_val=A[next_r][next_c]
            for j in dp[r][c]:
                dp[next_r][next_c].add(abs(j+next_val))
                dp[next_r][next_c].add(abs(j+next_val*-1))
            q.append((next_r,next_c))

print min(dp[H-1][W-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque,defaultdict

H,W=map(int, sys.stdin.readline().split())
A=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]
B=[ map(int, sys.stdin.readline().split()) for _ in range(H) ]

for h in range(H):
    for w in range(W):
        A[h][w]=abs(A[h][w]-B[h][w])

dp=[ [ 0 for _ in range(W) ] for __ in range(H) ]

Center=80*80      #中心地のセット マイナスの値もセットできるようにbitsetのゼロを80*80+1桁目に置く

#初期化
r,c=0,0
val=A[r][c]
dp[r][c]=1<<val+Center

q=deque()
q.append((0,0))
D=[(1,0),(0,1)]
Visit=defaultdict(lambda: 0)     #訪問済みの頂点にフラグ1を立てる
Visit[(0,0)]=1
D=[(1,0),(0,1)]

for r in range(H):
    for c in range(W):
        for dr,dc in D: #横に1つ移動か、下に1つ移動
            if r+dr<H and c+dc<W:   #移動しようとするマスが存在するならばif文内の処理を行う
                next_r=r+dr
                next_c=c+dc
                next_val=A[next_r][next_c]
                dp[next_r][next_c]|=dp[r][c]<<next_val  #次のマスの値が+の場合は、bitshift全体を左にシフト
                dp[next_r][next_c]|=dp[r][c]>>next_val  #次のマスの値が-の場合は、bitshift全体を右にシフト
                q.append((next_r,next_c))

ans=float("inf")
for i in range(Center*2):
    bit=dp[H-1][W-1]>>i&1
    if bit==1:
        ans=min(ans,abs(i-Center))

print ans
### BUGGY CODE ###

from sys import maxsize as INF

def main():
    N,K = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [INF]*N
    cost[0] = 0

    for j in range(1,N):
        for i in range(1,min(j,K)+1):
            cp = cost[j-i] + abs(h[j]-h[j-i])
            if cost[j] > cp : cost[j] = cp
        
    print(cost[-1])

    return

if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import maxsize as INF

def main():
    N,K = map(int, input().split())
    h = list(map(int, input().split()))
    cost = [INF]*N
    cost[0] = 0

    for j in range(1,N):
        for i in range(1,min(j,K)+1):
            cp = cost[j-i] + abs(h[j]-h[j-i])
            if cost[j] > cp : cost[j] = cp
        
    print(cost[-1])

    return

if __name__ == "__main__":
    main()
### BUGGY CODE ###

input_lines=list(map(int,input().split()))
balls=[]
count=0
for i in range(10**100):
    for j in range(input_lines[1]):
        balls.append('b')
    for j in range(input_lines[2]):
        balls.append('r')
    if len(balls)>input_lines[0]:
        break
for i in range(input_lines[0]):
    if balls[i]=='b':
        count+=1
print(count)

### FIXED CODE ###

n,a,b=map(int,input().split())
answer=n//(a+b)*a+min(n%(a+b),a)
print(answer)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline()

N = int(input())
S = list(input().strip())
Q = int(input())

for i in range(Q):
    q, a, b = map(str, input().split())
    if int(q) == 1:
        a = int(a) - 1
        S[a] = b
    if int(q) == 2:
        a = int(a) - 1
        b = int(b) - 1
        _set = set(S[a: b+1])
        print(len(_set))


### FIXED CODE ###

class SegmentTree:
    def __init__(self, data):
        # 単位元
        self.ide_ele = 0
        # num: n以上の最小の2のべき乗
        self.num = 2 ** (N - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(N):
            self.seg[i + self.num - 1] = 1 << (ord(data[i]) - 97)
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.seg[2 * i + 1] | self.seg[2 * i + 2]

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = 1 << (ord(x) - 97)
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.seg[k * 2 + 1] | self.seg[k * 2 + 2]

    def query(self, left, right):
        if right <= left:
            return self.ide_ele
        left += self.num - 1
        right += self.num - 2
        res = self.ide_ele
        while right - left > 1:
            if left & 1 == 0:
                res = res | self.seg[left]
            if right & 1 == 1:
                res = res | self.seg[right]
                right -= 1
            left = left // 2
            right = (right - 1) // 2
        if left == right:
            res = res | self.seg[left]
        else:
            res = (res | self.seg[left]) | self.seg[right]
        return res


N = int(input())
S = list(input().strip())
Q = int(input())
MAX_DIGIT = 26
st = SegmentTree(S)


for i in range(Q):
    q, a, b = map(str, input().split())
    if int(q) == 1:
        a = int(a) - 1
        st.update(a, b)
    if int(q) == 2:
        a = int(a) - 1
        b = int(b)
        res = st.query(a, b)
        print(str(bin(res)).count('1'))
### BUGGY CODE ###

n=int(input())
l=[]
for i in range(n):
    s=input()
    ss=sorted(s)
    l.append([ss])
ans=0
for i in range(n):
    for j in range(n):
        if i<j:
             if l[i]==l[j]:
                 ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
l={}
ans=0
for i in range(n):
  s=input()
  ss=sorted(s)
  s="".join(ss)
  ans+=l.setdefault(s, 0) 
  l[s]+=1
print(ans)
### BUGGY CODE ###

s = list(map(int, input().split()))
q = 0
if s[0] > 0 and s[0] - s[1] * s[2] > 0:
    print(s[0] - s[1] * s[2])
elif s[0] < 0 and s[0] + s[1] * s[2] < 0:
    print(-s[0] - s[1] * s[2])
else:
    if s[0] > 0:
        while s[0] - s[2] > 0:
            s[0] = s[0] - s[2]
            q = q + 1
        if (s[1] - q) % 2 == 1:
            print(-s[0]+s[2])
        else:
            print(s[0])
    elif s[0] < 0:
        while s[0] + s[2] < 0:
            s[0] = s[0] + s[2]
            q = q + 1
        if (s[1] - q) % 2 == 1:
            print(s[0]+s[2])
        else:
            print(-s[0])
    else:
        if s[1] % 2 == 1:
            print(s[2])
        else:
            print(s[0])

### FIXED CODE ###

s = list(map(int, input().split()))
r = s[0] // s[2] 
t = s[0] % s[2] 
if s[0] > 0 and s[0] - s[1] * s[2] > 0:
    print(s[0] - s[1] * s[2])
elif s[0] < 0 and s[0] + s[1] * s[2] < 0:
    print(-s[0] - s[1] * s[2])
else:
    if s[0] > 0:
        r = s[0] // s[2] 
        t = s[0] % s[2] 
        if (s[1] - r) % 2 == 1:
            print(-t + s[2])
        else:
            print(t)
    elif s[0] < 0:
        v = (-s[0]) // s[2]
        w = -((-s[0]) % s[2])
        if (s[1] - v) % 2 == 1:
            print(w+s[2])
        else:
            print(-w)
    else:
        if s[1] % 2 == 1:
            print(s[2])
        else:
            print(s[0])
### BUGGY CODE ###

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def bfs(src):
    from collections import deque

    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    que = deque()
    h, w = src
    que.append((dist[h][w], h, w))
    while que:
        cost, h, w = que.popleft()
        for dh, dw in directions:
            h2 = h + dh
            w2 = w + dw
            if h2 < 0 or w2 < 0 or h2 >= N or w2 >= N:
                continue
            if dist[h2][w2] > cost:
                dist[h2][w2] = cost
                que.append((cost+seated[h2][w2], h2, w2))

N = INT()
P = [p-1 for p in LIST()]

dist = list2d(N, N, 0)
for i in range(N):
    for j in range(N):
        dist[i][j] = min(i, N-i-1, j, N-j-1)

ans = 0
seated = list2d(N, N, 1)
for p in P:
    h, w = p//N, p%N
    ans += dist[h][w]
    bfs((h, w))
    seated[h][w] = 0
print(ans)


### FIXED CODE ###

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

def bfs(src):
    from collections import deque

    que = deque()
    h, w = src
    que.append((dist[h][w], h, w))
    while que:
        cost, h, w = que.popleft()
        if h > 1:
            if dist[h-1][w] > cost:
                dist[h-1][w] = cost
                que.append((cost+seated[h-1][w], h-1, w))
        if h < N-1:
            if dist[h+1][w] > cost:
                dist[h+1][w] = cost
                que.append((cost+seated[h+1][w], h+1, w))
        if w > 1:
            if dist[h][w-1] > cost:
                dist[h][w-1] = cost
                que.append((cost+seated[h][w-1], h, w-1))
        if w < N-1:
            if dist[h][w+1] > cost:
                dist[h][w+1] = cost
                que.append((cost+seated[h][w+1], h, w+1))

N = INT()
P = [p-1 for p in LIST()]

dist = list2d(N, N, 0)
for i in range(N):
    for j in range(N):
        dist[i][j] = min(i, N-i-1, j, N-j-1)

ans = 0
seated = list2d(N, N, 1)
for p in P:
    h, w = divmod(p, N)
    ans += dist[h][w]
    bfs((h, w))
    seated[h][w] = 0
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())

pat = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if s == x + y + z :
                pat += 1
print(pat)

### FIXED CODE ###

k, s = map(int, input().split())

pat = 0
for x in range(k+1):
    for y in range(k+1):
            if 0 <= s - (x + y) <= k:
                pat += 1
print(pat)
### BUGGY CODE ###

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

if sum(map(sum, S)) <= K:
    print(0)
    exit(0)

def satisfy(left, right, horizons):
    global K, S
    top = 0
    for idx, h in enumerate(horizons):
        if h == 1:
            bottom = idx
            total = sum(map(lambda row: sum(
                row[left:(right + 1)]), S[top:(bottom + 1)]))
            # print(horizons, top, bottom, left, right, total)
            if total > K:
                return False
            top = bottom + 1
    total = sum(map(lambda row: sum(row[left:(right + 1)]), S[top:]))
    # print(horizons, top, -1, left, right, total)
    if total > K:
        return False
    return True

# ex. horizons = [0, 0, 1, 0, 0, 1]
def greedy(horizons):
    answer = sum(horizons)
    left = 0
    right = 0
    # greedyに縦線を引いていく
    # 無理(ブロックの中のホワイトチョコの数をk以下にできない)だったら-1を返す
    while right <= W - 1:
        if not satisfy(left, right, horizons):
            if left == right:
                return -1
            left = right
            answer += 1
        else:
            right += 1
    return answer

answer = (H - 1) * (W - 1)

# result = greedy([0, 1, 0])

for i in range(0, 2 ** (H - 1)):
    horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
    result = greedy(horizons)
    if result > 0 and result < answer:
        answer = result

print(answer)


### FIXED CODE ###

import numpy as np

def main():
    H, W, K = 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)
        exit(0)
    answer = float('INF')
    for i in range(0, 2 ** (H - 1)):
        horizons = list(map(int, list(bin(i)[2:].zfill(H - 1))))
        result = greedy(W, S, K, horizons, answer)
        answer = min(answer, result)
    print(answer)

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

if __name__ == '__main__':
    main()