Harryxun/stf_run huggingface dataset:
import sys
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

input = sys.stdin.readline

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, M = inpl()
graph = [[] for i in range(N+1)]

for i in range(M):
    x, y = inpl()
    graph[x].append(y)

flag = [False] * (N + 1)
dp = [0] * (N + 1)


def f(x):
    if flag[x]:
        return dp[x]
    flag[x] = True
    fans = 0
    for y in graph[x]:
        fans = max(fans, f(y) + 1)
    dp[x] = fans
    return dp[x]

ans = 0
for i in range(1, N + 1):
    ans = max(ans, f(i))
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from heapq import heappush, heappop, heapify
import math
from math import gcd
import itertools as it
import collections
from collections import deque 

def inp():
    return int(input())
def inpl():
    return list(map(int, input().split()))
def _debug(obj):
    print(obj, file=sys.stderr)

# ---------------------------------------

N, M = inpl()
graph = [[] for i in range(N+1)]

for i in range(M):
    x, y = inpl()
    graph[x].append(y)

flag = [False] * (N + 1)
dp = [0] * (N + 1)


def f(x):
    if flag[x]:
        return dp[x]
    flag[x] = True
    fans = 0
    for y in graph[x]:
        fans = max(fans, f(y) + 1)
    dp[x] = fans
    return dp[x]

ans = 0
for i in range(1, N + 1):
    ans = max(ans, f(i))
print(ans)
a= input()
s=input()

if a<3200:
  print("red")
else:
  print(s)

### FIXED CODE ###

a=int(input())
s=input()

if a<3200:
  print("red")
else:
  print(s)
import math
import sys
import itertools
import numpy as np
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

s = S()
x,y = IL()
N = len(s)

xlist = []
ylist = []

f = 0
cnt = 0
for i in range(N):
  if s[i] == "F":
    cnt += 1
  elif s[i] == "T":
    if f == 0:
      xlist.append(cnt)
      f = 1
    else:
      ylist.append(cnt)
      f = 0
    cnt = 0
else:
  if f == 0:
    xlist.append(cnt)
  else:
    ylist.append(cnt)

#print(xlist)
#print(ylist)

Xsum = sum(xlist)
Ysum = sum(ylist)

if (Xsum-x)%2 != 0:
  print("No")
  exit()
else:
  Xnum = (Xsum-x)//2
if (Ysum-y)%2 != 0:
  print("No")
  exit()
else:
  Ynum = (Ysum-y)//2

XDP = np.array([[0]*(Xnum+1) for _ in range(len(xlist)+1)])
YDP = [[0]*(Ynum+1) for _ in range(len(ylist)+1)]
XDP[0][0] = 1
YDP[0][0] = 1

for i in range(1,len(xlist)+1):
  for j in range(Xnum+1):
    if XDP[i-1][j] == 1:
      XDP[i][j] = 1
      if j+xlist[i-1] < Xnum+1:
        XDP[i][j+xlist[i-1]] = 1
#print(XDP)
for i in range(1,len(ylist)+1):
  for j in range(Ynum+1):
    if YDP[i-1][j] == 1:
      YDP[i][j] = 1
      if j+ylist[i-1] < Ynum+1:
        YDP[i][j+ylist[i-1]] = 1
#print(YDP)
if XDP[-1][-1] == 1 and YDP[-1][-1] == 1:
  print("Yes")
else:
  print("No")
"""
FFTFFTFFFFTFFFFTFFTFFTFFFFTFFFFTFFTFF
2 2

"""

### FIXED CODE ###

#import numpy as np
import math
import sys
import itertools
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

s = S()
x,y = IL()
N = len(s)

xlist = []
ylist = []

f = 0
cnt = 0
for i in range(N):
  if s[i] == "F":
    cnt += 1
  elif s[i] == "T":
    if f == 0:
      xlist.append(cnt)
      f = 1
    else:
      ylist.append(cnt)
      f = 0
    cnt = 0
else:
  if f == 0:
    xlist.append(cnt)
  else:
    ylist.append(cnt)

x -= xlist.pop(0)
Xsum = sum(xlist)
Ysum = sum(ylist)

if (Xsum-x)%2 != 0:
  print("No")
  exit()
else:
  Xnum = (Xsum-abs(x))//2
if (Ysum-y)%2 != 0:
  print("No")
  exit()
else:
  Ynum = (Ysum-abs(y))//2

#print(Xnum,Ynum)

XDP = [[0]*(abs(Xnum)+1) for _ in range(len(xlist)+1)]
YDP = [[0]*(abs(Ynum)+1) for _ in range(len(ylist)+1)]

XDP[0][0] = 1
YDP[0][0] = 1

for i in range(1,len(xlist)+1):
  for j in range(Xnum+1):
    if XDP[i-1][j] == 1:
      XDP[i][j] = 1
      if j+xlist[i-1] < Xnum+1:
        XDP[i][j+xlist[i-1]] = 1
#print(Xnum)
#print(xlist)
#print(XDP)

for i in range(1,len(ylist)+1):
  for j in range(Ynum+1):
    if YDP[i-1][j] == 1:
      YDP[i][j] = 1
      if j+ylist[i-1] < Ynum+1:
        YDP[i][j+ylist[i-1]] = 1
#print(Ynum)
#print(ylist)
#print(YDP)

if XDP[-1][-1] == 1 and YDP[-1][-1] == 1:
  print("Yes")
else:
  print("No")
N = int(input())
S = input()
def count(_S):
    _S = input().rstrip('#').lstrip('.')
    if len(_S) == 0 :
        return 0
    numSW = _S.count('.')
    numSB = _S.count('#')
    SR = _S.lstrip('#').rstrip('.')
    numSR = len(_S) - len(SR)
    if numSW <= numSB and numSW <= numSR:
        return numSW
    elif numSB <= numSW and numSB <= numSR:
        return numSB
    else:
        return numSR + count(SR)
print(count(S))

### FIXED CODE ###

_ = input()
S = input()
numc = S.count('.')
numcmin = numc
for s in S:
    if s == '#':
        numc = numc + 1
    else:
        numc = numc -1
        if numc < numcmin:
            numcmin = numc
print(numcmin)
scores=[]
def depth(now,score,d):
    global scores
    if d[now]:
        for i in d[now]:
            depth(i,score+1,d)
    else:
        scores.append(score)
        return 


N,M=map(int,input().split())
d=[[] for i in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    d[x-1].append(y-1)

Max=0
for i in range(N):
    depth(i,0,d)
    if scores and max(scores)>Max:
        Max=max(scores)
    scores=[]
print(Max)

### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(100000)
N,M=map(int,input().split())
d=[[] for i in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    d[x-1].append(y-1)
dp=[0 for i in range(N)]

def depth(now,score,d):
    global dp
    if dp[now]==0 or not(dp[now]):
        if d[now]:
            _score=[]
            for i in d[now]:
                _score.append(depth(i,score+1,d)-score)
            dp[now]=max(_score)
        else:
            return score

        return dp[now]+score

    else:
        return dp[now]+score



Max=0
for i in range(N):
    m=depth(i,0,d)
    if  m>Max:            
        Max=m
print(Max)
S = list(input())
if S[0]==s[1] or S[1]==S[2] or S[2]==S[3]:
  print('Bad')
else:
  print('Good')

### FIXED CODE ###

S = list(input())
if S[0]==S[1] or S[1]==S[2] or S[2]==S[3]:
  print('Bad')
else:
  print('Good')
def can(x):
    i = min(n,x)
    end = min(m,i)
    t = a[i]+b[x-i]
    for k in range(x-i,end+1):
        t = min(t, a[i]+b[k])
        i -= 1
    if t<=k:
        return True
    else:
        return False

n,m,k=map(int,input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
a = [0]+a
for i in range(1,n+1):
    a[i] += a[i-1]
b = [0]+b
for i in range(1,m+1):
    b[i] += b[i-1]

lo = 0
hi = n+m
while lo<hi:
    mid=lo+((hi-lo+1)>>1)
    if can(mid):
        lo=mid
    else:
        hi = mid-1
print(lo)


### FIXED CODE ###

n,m,k=map(int,input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
a = [0]+a
for i in range(1,n+1):
    a[i] += a[i-1]
b = [0]+b
for i in range(1,m+1):
    b[i] += b[i-1]

ans,j = 0,m
for i in range(n+1):
    if a[i] > k:
        break
    while b[j] > k-a[i]:
        j -= 1
    ans = max(ans,i+j)
print(ans)
print("Yes" if len(set(input()) == 3 else "No")

### FIXED CODE ###

print("Yes" if len(set(input())) == 3 else "No")
l = []
for i in range(10):
    inp = input()
    l.append(int(inp))
l.sort().reverse()
for i in range(3):
    print(l[i])

### FIXED CODE ###

l = []
for i in range(10):
    inp = input()
    l.append(int(inp))
l.sort()
l.reverse()
for i in range(3):
    print(l[i])
s = input()

list = ["Sunny","Cloudy","Rainy"]

result = list.index(s)%3

print(list[result + 1])

### FIXED CODE ###

s = input()

list = ["","Sunny","Cloudy","Rainy"]

result = list.index(s)%3

print(list[result+1])
import math
a,b,x = map(int,input().split())
s = a*a*b
if x*2 <= s :
    ans = 90 - math.degrees(math.atan(2*x/(a*b*b)))
else :
    ans = 90 - math.degrees(math.atan(a**3/(s-x)/2))
print(ans)


### FIXED CODE ###

import math
a,b,x = map(int,input().split())
s = a*a*b
if x*2 < s :
    ans = 90 - math.degrees(math.atan(2*x/(a*b*b)))
elif x == s :
    ans = 0
else :
    ans = 90 - math.degrees(math.atan(a**3/(s-x)/2))
print(ans)
n=int(input())
a=list(map(int,input().split()))
cnt=0
for i in range(n-1):
  if a[i]==a[i+1]:
    a[i+1]=a[i]+a[i+2]
    cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=[ int(i) for i in range(10000)]
b=set(a)
for j in b:
  l.remove(j)
cnt=0
for i in range(1,n):
  if a[i-1]==a[i]:
    a[i]=l.pop()
    cnt+=1
print(cnt)
while True:
    table=str(input())
    if table[0] == '0':
        break
    print(sum(int(num) for num in table(num)))



### FIXED CODE ###

while True:
    table=str(input())
    if table[0] == '0':
        break
    print(sum(int(num) for num in(table)))
import numpy as np
def main():
N,K = map(int, input().split())
p = np.array(list(map(int,input().split())))
p = (p+1)/2
ans = 0.0
for i in range(N-K+1):
    buf = sum(p[i:i+K])
    if ans < buf:
        ans = buf
print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
N,K = map(int, input().split())
p = [(int(i)+1)/2 for i in input().split()]
s = [0]*N
s[0] = p[0]
if N==K:
    print(sum(p))
else:
    for i in range(N-1):
        s[i+1] = s[i]+p[i+1]
    ans=max(s[i+K]-s[i] for i in range(N-K))
    print(ans)
#!/usr/bin/env python3
def main():
    def search_loop(now: int, loop: list):
        """iから探索を初めて，再びiに達するまでに通った点のスコアをリストとして返す"""
        seen[now] = True
        if now == i and loop:
            loops.append(loop)
            return
        loop.append(C[now])
        search_loop(P[now], loop)

    N, K = map(int, input().split())
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    # ループを探す
    seen = [False] * N
    loops = []
    for i in range(N):
        if seen[i] is False:
            search_loop(i, [])

    # ループごとの最大スコアを探す
    ans = -10 ** 9
    for loop in loops:
        length = len(loop)
        sum_loop = sum(loop)
        # ループ長よりも操作回数が多く，ループを周回すると得な場合
        if K > length and sum_loop > 0:
            res = sum_loop * (K // length)
            limit = K % length
        # そうじゃない場合
        else:
            res = 0
            limit = K

        loop_temp = loop * 3  # loopリストに同じloopリストを接続する
        for k in range(1, limit + 1):
            for i in range(length):
                ans = max(ans, sum(loop_temp[i:i + k]) + res)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = -10 ** 9
    for start in range(N):
        # ループを探す
        now = start
        loop = []
        total = 0
        while now != start or not loop:
            loop.append(C[now])
            now = P[now]
            total += C[now]
        # ループごとの最大スコアを探す
        length = len(loop)
        # sum_loop = sum(loop)
        # # ループ長よりも操作回数が多いか？，ループを周回すると得か？で場合分け
        # res = 0 if sum_loop <= 0 else sum_loop * (K // length)
        # limit = K if K <= length else K % length
        # for k in range(limit):
        #     res += loop[k]
        #     ans = max(ans, res)
        t = 0
        for i in range(length):
            t += loop[i]
            if i + 1 > K:
                break
            now = t
            if total > 0:
                e = (K - (i + 1)) // length
                now += total * e
            ans = max(ans, now)
    print(ans)


if __name__ == '__main__':
    main()
inp=input()
a = int(inp[0])
b = int(inp[1])
if a < b:
    print("a < b")
elif a > b:
    print("a > b")
else:
    print("a == b")

### FIXED CODE ###

inp=input().split()
a = int(inp[0])
b = int(inp[1])
if a < b:
    print("a < b")
elif a > b:
    print("a > b")
else:
    print("a == b")
def calc(a, b):
    if a <= 0 or b <= 0:
        return 0
    if a == b:
        return a
    a, b = min(a, b), max(a, b)
    return calc(b-a, a) + 2 * a

N, X = map(int, raw_input().split())
print calc(X, N-X) + N 


### FIXED CODE ###

def calc(a, b):
    if a <= 0 or b <= 0:
        return 0
    if a == b:
        return a
    a, b = min(a, b), max(a, b)
    x = max(1, b / (2 * a))
    return calc(b-x*a, a) + 2 * a * x

N, X = map(int, raw_input().split())
print calc(X, N-X) + N
a,b=list(map(int,input().split()))

from fractions import gcd

res=a*b/math.gcd(a,b)
print(int(res))



### FIXED CODE ###


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

from fractions import gcd

res=a*b/gcd(a,b)
print(int(res))
import numpy as np

N=int(input())

A=list(map(int,input().split()))

A=np.array(A)

B=np.identity(N)

for i in range(N-1):
    B[i][i+1]=1
B[N-1][0]=1

B_inv=np.linalg.inv(B)

A=A.reshape((1,N))
X=2*np.dot(B_inv,A.transpose())

X=list(map(int,X))

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


### FIXED CODE ###

N=int(input())

A=list(map(int,input().split()))

B=[sum(A)]

for i in range(1,N,2):
    B[0]-=2*A[i]

for i in range(N-1):
    B.append(2*A[i]-B[i])

print(' '.join(map(str,B)))
#入力
HPlist = list(map(int, input().split()))
HPlist[0] = A
HPlist[1] = B
HPlist[2] = C
HPlist[3] = D

int aokiDeath
int takahashiDeath

#高橋の攻撃何発分か
if C % B == 0:
    aokiDeath = C // B
else:
    aokiDeath = C // B + 1 

#青木の攻撃何回分か
if A % D == 0:
    takahashiDeath = A // D
else:
    takahashiDeath = A // D + 1

if aokiDeath <= takahashiDeath:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

#入力
S, W = map(int, input().split())

if W >= S:
    print("unsafe")
else:
    print("safe")
#最大の最小値を求める問題は二部探索
#最大の最小値がちょうどokとngの境界になる
#求める値をlとするとその長さに全ての丸太をきるのに必要な回数を数えることができる
#その丸太をきる回数がk回以下であればいい
#絶対にだめ→０　絶対にオッケー→max(a)
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
#丸太をきる回数がk回以下かどうか調べる関数
def check(n):
  cnt=0
  for l in a:
    if l%n==0:
      cnt=cnt+l//n-1
    else:
      cnt=cnt+l//n
  if cnt<=k:
    return True
  else:
    return False
#二部探索  
left=-1
right=max(a)+1
while right-left>1:
  mid=(right+left)//2
  if check(mid):
    right=mid
  else:
    left=mid
print(right)
  


### FIXED CODE ###

#最大の最小値を求める問題は二部探索
#最大の最小値がちょうどokとngの境界になる
#求める値をlとするとその長さに全ての丸太をきるのに必要な回数を数えることができる
#その丸太をきる回数がk回以下であればいい
#絶対にだめ→０　絶対にオッケー→max(a)
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
#丸太をきる回数がk回以下かどうか調べる関数
def check(n):
  cnt=0
  for l in a:
    if l%n==0:
      cnt=cnt+l//n-1
    else:
      cnt=cnt+l//n
  if cnt<=k:
    return True
  else:
    return False
#二部探索  
left=0
right=max(a)
while right-left>1:
  mid=(right+left)//2
  if check(mid):
    right=mid
  else:
    left=mid
print(right)
s=input().split();n,a,b=int(s[0]),int(s[1]),int(s[2])
if a>b:
    print(0)
elif n=1:
    if a==b:
        print(1)
    else:
        print(0)
else:
    print((a-b)*(n-2)+1)

### FIXED CODE ###

n,a,b=map(int,input().split())
if n>1 and b>=a or n==1 and a==b: 
    print ((n-2)*(b-a)+1);
else:
    print ("0");
s = input()
if s.endswith(2,4,5,7,9) == True:
  print('hon')
elif s.endswith(0,1,6,8) == True:
  print('pon')
else:
  print('bon')

### FIXED CODE ###

s = input()
n = len(s)
a = s[n-1:n]
if a == '2' or a == '4' or a == '5' or a == '7' or a == '9':
  print('hon')
elif a == '0' or a == '1' or a == '6' or a == '8':
  print('pon')
else:
  print('bon')
import math

n, m = map(int, input().split())

ans = n*(n-1)//2 + m(m-1)//2
print(ans)


### FIXED CODE ###

import math

n, m = map(int, input().split())


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


if m >= 2:
    odd = combinations_count(m, 2)
elif m == 0 or m == 1:
    odd = 0

if n >= 2:
    even = combinations_count(n, 2)
elif n == 1:
    even = 1
elif n == 0:
    even = 0

answer = odd + even
if m == 1 and n == 1:
    answer = 0

print(answer)
num = int(input())

s1 = input()
s2 = input()
ans=""
for i in range(num):
    ans+=s1[i]
    ans+=s2[i]

print(ans)


### FIXED CODE ###

num = int(input())
ans=""
(s1,s2) = input().split(" ")



for i in range(num):
    ans+=s1[i]
    ans+=s2[i]

print(ans)
import math
r = int(input())

print("%.6f %.6f"%(r*r*math.pi,2*r*math.pi))

### FIXED CODE ###

import math
r = float(input())

print("%.6f %.6f"%(r*r*math.pi,2*r*math.pi))
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

A.sort()
for i in range(M):
  cnt = 0
  for j in range(M):
    if cnt >= BC[i][0]:
      break
    if BC[i][1] > A[j]:
      A[j] = BC[i][1]
      cnt += 1
  if i != M-1:
    A.sort()
print(sum(A))

    

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

L = []
BC.sort(key=lambda x:x[1], reverse=True)
A.sort()
# ans = sum(A)
ans = 0
# flag = False
cnt = 0
# for k in range(N):
#     if k <= len_L-1:
#         if flag and L[k] > A[k]:
#             ans += L[k]
#         else:
#             flag = False
#             ans += A[k]
#     else:
#         ans += A[k]
for i in range(M):
    for j in range(BC[i][0]):
        if cnt < N and A[cnt] < BC[i][1]:
            ans += BC[i][1]
            cnt += 1
        else:
            break
    else:
        continue
    break

if cnt < N:
    ans += sum(A[cnt::])

print(ans)
n = int(input())
ai = [int(i) for i in input().split()]

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0]+ai[2],ai[1]))
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()

dp[1][0] = ai[0]
dp[1][1] = ai[1]

if is_odd == True:
    for i in range(n+n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-2][0],dp[n-1][1],dp[n-1][2]))
else:
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-1][0],dp[n-1][1]))



### FIXED CODE ###

n = int(input())
ai = [int(i) for i in input().split()]

is_odd = True

if n % 2 == 0:
    is_odd = False

if is_odd == True:
    dp = [[0 for i in range(3)] for j in range(n)]
else:
    dp = [[0 for i in range(2)] for j in range(n)]

if n == 3:
    print(max(ai[0],ai[2],ai[1]))
    exit()
elif n == 2:
    print(max(ai[0],ai[1]))
    exit()
    

if is_odd == True:
    dp[0][0] = ai[0]
    dp[1][1] = ai[1]
    dp[2][0] = ai[0]+ai[2]
    dp[2][2] = ai[2]
    dp[3][1] = max(ai[0]+ai[3],ai[1]+ai[3])    
    for i in range(4,n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
        dp[i][2] = max(dp[i-4][0]+ai[i],dp[i-3][1]+ai[i],dp[i-2][2]+ai[i])
    print(max(dp[n-3][0],dp[n-2][1],dp[n-1][2]))
else:
    dp[0][0] = ai[0]
    dp[1][1] = ai[1]
    dp[2][0] = ai[0]+ai[2]       
    for i in range(n):
        dp[i][0] = dp[i-2][0]+ai[i]
        dp[i][1] = max(dp[i-2][1]+ai[i],dp[i-3][0]+ai[i])
    print(max(dp[n-2][0],dp[n-1][1]))
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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

def max(iterable):
    ma = 0
    for i in iterable:
        ma = max(ma, i)
    return ma

for i in range(2 ** (H - 1)):
    # div[j] is true if row j and row j + 1 is divided
    div = [(i & (1 << j)) > 0 for j in range(H - 1)]
    group = [0] * H
    for j in range(H - 1):
        group[j + 1] = group[j] + 1 if div[j] else group[j]
    count = Counter()
    ans = div.count(True)
    ok = True
    for j in range(W):
        tmp = Counter()
        for k in range(H):
            if S[k][j] == '1':
                tmp[group[k]] += 1
        if max(tmp.values()) > K:
            ok = False
        elif max((tmp + count).values()) <= K:
            count += tmp
        else:
            count = tmp
            ans += 1
    if ok and (mi is None or ans < mi):
        mi = ans

print(mi)


### FIXED CODE ###

import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
from math import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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

def _max(iterable):
    ma = 0
    for i in iterable:
        ma = max(ma, i)
    return ma

for i in range(2 ** (H - 1)):
    # div[j] is true if row j and row j + 1 is divided
    div = [(i & (1 << j)) > 0 for j in range(H - 1)]
    group = [0] * H
    for j in range(H - 1):
        group[j + 1] = group[j] + 1 if div[j] else group[j]
    count = Counter()
    ans = div.count(True)
    ok = True
    for j in range(W):
        tmp = Counter()
        for k in range(H):
            if S[k][j] == '1':
                tmp[group[k]] += 1
        if _max(tmp.values()) > K:
            ok = False
        elif _max((tmp + count).values()) <= K:
            count += tmp
        else:
            count = tmp
            ans += 1
    if ok and (mi is None or ans < mi):
        mi = ans

print(mi)
# coding: utf-8
# Your code here!
N=int(input())
l=list(map(int,input().split()))

if temp[0]==0:
    print(0)
    exit()

ans=1
for i in range(2,len(temp)):
    #print(ans)
    ans=ans*temp[i-1]**temp[i]
print(ans)



### FIXED CODE ###

N=int(input())
D=list(map(int,input().split()))
layer=[0]*N

mx=0
for item in D:
    layer[item]+=1
    mx=max(mx,item)

if layer[0]!=1 or D[0]!=0:
    print(0)
    exit()

ans=1
for i in range(mx):
    ans*=(layer[i]**layer[i+1])

print(ans%998244353)
pi = 3.14159265358979
r = int(input())
area = pi * r**2 
circumference = 2 * pi * r
print(area, circumference)

### FIXED CODE ###

import math

r = float(input())

area = math.pi * r**2
diameter =  2 * math.pi * r

print(area, diameter)
if __name__ == '__main__':
    n, a, b = input().split()
    N, A, B = int(n), int(a), int(b)

    ans_max = min(A, B)

    n_mid = N / 2
    if (A + B) <= N
        ans_min = 0
    else:
        ans_min = max((A - n_mid) + (B - n_mid), 0)

    print('{0} {1}'.format(ans_max, ans_min))


### FIXED CODE ###

if __name__ == '__main__':
    n, a, b = input().split()
    N, A, B = int(n), int(a), int(b)

    ans_max = min(A, B)

    if (A + B) <= N:
        ans_min = 0
    else:
        ans_min = max((A + B - N), 0)

    print('{0} {1}'.format(ans_max, ans_min))
import math
a,b,c,d = map(int, raw_input().split())

length = math.sqrt((a - c) ** 2 + (b - d) ** 2)
print length

### FIXED CODE ###

import math
a,b,c,d = map(float, raw_input().split())

length = math.sqrt((a - c) ** 2 + (b - d) ** 2)
print length
d,g = map(int,input().split())
"""
PC = []
for i in range(d):
    pc = list(map(int,input().split()))
    PC.append(pc)
"""
PC =[list(map(int,input().split())) for i in range(d)]

def solve(G,i):
    if i<=0:
        return float('inf')
    n = min(int(G/100*i),PC[i-1][0])
    score = 100 * i * n 
    if n == PC[i-1][0]:
        score += PC[i-1][1]
    if G > score:
        n += solve(G-score,i-1)
    return min(n,solve(G,i-1))

print(solve(G,D))

### FIXED CODE ###

d,g = map(int,input().split())
"""
PC = []
for i in range(d):
    pc = list(map(int,input().split()))
    PC.append(pc)
"""
PC =[list(map(int,input().split())) for i in range(d)]

def solve(g,i):
    if i<=0:
        return float('inf')
    n = min(int(g/(100*i)),PC[i-1][0])
    score = 100 * i * n
    if n == PC[i-1][0]:
        score += PC[i-1][1]
    if g > score:
        n += solve(g-score,i-1)
    return min(n,solve(g,i-1))

print(solve(g,d))