Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(input()) for _ in range(N)]

c = 0
n = 1
checked = [False for _ in range(N)]
checked[0] = True
for _ in range(N+1):
    n = A[n-1]
    c += 1
    if n == 2:
        ok = True
        break
    if checked[n-1]:
        ok = False
        break
if ok:
    print(c)
else:
    print(-1)

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]

c = 0
n = 1
checked = [False for _ in range(N)]
checked[0] = True
for _ in range(N+1):
    n = A[n-1]
    c += 1
    if n == 2:
        ok = True
        break
    if checked[n-1]:
        ok = False
        break
    checked[n-1] = True
if ok:
    print(c)
else:
    print(-1)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(input()) for _ in range(N)]

c = 0
n = 1
for _ in range(N+1):
    n = A[n-1]
    c += 1
    if n == 1:
        ok = False
        break
    if n == 2:
        ok = True
        break
if ok:
    print(c)
else:
    print(-1)

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]

c = 0
n = 1
checked = [False for _ in range(N)]
checked[0] = True
for _ in range(N+1):
    n = A[n-1]
    c += 1
    if n == 2:
        ok = True
        break
    if checked[n-1]:
        ok = False
        break
    checked[n-1] = True
if ok:
    print(c)
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [int(input()) for _ in range(N)]

c = 0
n = 1
while True:
    n = A[n-1]
    c += 1
    if n == 1:
        ok = False
        break
    if n == 2:
        ok = True
        break
if ok:
    print(c)
else:
    print(-1)

Fixed submission:
N = int(input())
A = [int(input()) for _ in range(N)]

c = 0
n = 1
checked = [False for _ in range(N)]
checked[0] = True
for _ in range(N+1):
    n = A[n-1]
    c += 1
    if n == 2:
        ok = True
        break
    if checked[n-1]:
        ok = False
        break
    checked[n-1] = True
if ok:
    print(c)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
N, A, B = map(int, input().split())
H = [int(input()) for _ in range(N)]

l = 0
r = max(H)

while r > l+1:
    T = (l+r)//2
    c = 0
    for h in H:
        if h > B*T:
            c += (h-B*T)//(A-B)
            if (h-B*T)%(A-B) != 0:
                c += 1
    if c <= T:
        r = T
    else:
        l = T

if l == T:
    print(T+1)
else:
    print(T)

Fixed submission:
N, A, B = map(int, input().split())
H = [int(input()) for _ in range(N)]

l = 0
r = max(H)
T = 1
while r > l+1:
    T = (l+r)//2
    c = 0
    for h in H:
        if h > B*T:
            c += (h-B*T)//(A-B)
            if (h-B*T)%(A-B) != 0:
                c += 1
    if c <= T:
        r = T
    else:
        l = T

if l == T:
    print(T+1)
else:
    print(T)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

mod = 10**9+7

N, M = map(int, input().split())
LRX = [list(map(int, input().split())) for _ in range(M)]

LX = [[] for _ in range(N+2)]
for l, r, x in LRX:
    LX[r].append((l, x))

dp = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
# dp[i][j][k] (i <= j <= k) 
# 三色それぞれ、最後に使ったindex(1-indexed)がi,j,k

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

# (i, j, k+1)に置くのが、条件(l,x)に適しているか
def check(i, j, l, x):
    return (x == 3 and l <= i) or (x == 2 and i < l <= j) or (x == 1 and j < l)

for i in range(N+1):
    for j in range(i, N+1):
        for k in range(j, N+1):
            
            # 一番前の色を置く
            ok = True
            for l, x in LX[k+1]:
                if not check(j, k, l, x):
                    ok = False
            if ok:
                dp[j][k][k+1] = (dp[j][k][k+1] + dp[i][j][k]) % mod
            
            # 最後
            ok = True
            for l, x in LX[k+1]:
                if not check(i, j, l, x):
                    ok = False
            if ok:
                dp[i][j][k+1] = (dp[i][j][k+1] + dp[i][j][k]) % mod
            
            # 二番目
            ok = True
            for l, x in LX[k+1]:
                if not check(i, k, l, x):
                    ok = False
            if ok:
                dp[i][k][k+1] = (dp[i][k][k+1] + dp[i][j][k]) % mod
        

                

ans = 0
for a in range(N+1):
    for b in range(N+1):
        ans = (ans + dp[a][b][N]) % mod

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

mod = 10**9+7



# (i, j, k+1)に置くのが、条件(l,x)に適しているか
def check(i, j, l, x):
    return (x == 3 and l <= i) or (x == 2 and i < l <= j) or (x == 1 and j < l)


N, M = map(int, input().split())
LRX = [list(map(int, input().split())) for _ in range(M)]

LX = [[] for _ in range(N+2)]
for l, r, x in LRX:
    LX[r].append((l, x))

dp = [[[0]*(j+1) for j in range(i+1)] for i in range(N+2)]
# dp[i][j][k] (k <= j <= i) 
# 三色それぞれ、最後に使ったindex(1-indexed)がi,j,k

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

for i in range(N+1):
    for j in range(i, N+1):
        for k in range(j, N+1):
            
            # 一番前の色を置く
            ok = True
            for l, x in LX[k+1]:
                if not check(j, k, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][k][j] = (dp[k+1][k][j] + dp[k][j][i]) % mod
            
            # 最後
            ok = True
            for l, x in LX[k+1]:
                if not check(i, j, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][j][i] = (dp[k+1][j][i] + dp[k][j][i]) % mod
            
            # 二番目
            ok = True
            for l, x in LX[k+1]:
                if not check(i, k, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][k][i] = (dp[k+1][k][i] + dp[k][j][i]) % mod
        

ans = 0
for a in range(N+1):
    for b in range(a,N+1):
        ans = (ans + dp[N][b][a]) % mod

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

q = []
checked = [-1]*N
for n in range(N):
    if len(graph[n]) == 1:
        q.append(n)
        checked[n] = 0

ok = False
while q:
    posiq = []
    for p in q:
        update = False
        for np in graph[p]:
            if checked[np] == -1:
                checked[np] = checked[p] + 1
                update = True
                posiq.append(np)
            elif checked[np] == checked[p] + 1:
                ok = True
                break
            elif checked[np] == checked[p]:
                update = True
        if not update:
            ok = True
            break
    
    q = set()
    for p in posiq:
        for np in graph[p]:
            if checked[np] == -1 and not np in q:
                c = 0
                for mp in graph[np]:
                    if checked[mp] == -1:
                        c += 1
                    if c >= 2: break
                if c <= 1:
                    q.append(np)
    for np in q:
        checked[np] = checked[p] + 1

print("First" if ok else "Second")            


Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

q = []
checked = [-1]*N
for n in range(N):
    if len(graph[n]) == 1:
        q.append(n)
        checked[n] = 0

ok = False
while q:
    posiq = []
    for p in q:
        update = False
        for np in graph[p]:
            if checked[np] == -1:
                checked[np] = checked[p] + 1
                update = True
                posiq.append(np)
            elif checked[np] == checked[p] + 1:
                ok = True
                break
            elif checked[np] == checked[p]:
                update = True
        if not update:
            ok = True
            break
    
    q = set()
    for p in posiq:
        for np in graph[p]:
            if checked[np] == -1 and not np in q:
                c = 0
                for mp in graph[np]:
                    if checked[mp] == -1:
                        c += 1
                    if c >= 2: break
                if c <= 1:
                    q.add(np)
    for np in q:
        checked[np] = checked[p] + 1

print("First" if ok else "Second")
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

def count(s):
    ans = 0
    for i, a in enumerate(A):
        if i == 0:
            continue
        if s < 0:
            if 1-s-a >= 0:
                ans += 1-s-a
                s = 1
            else:
                s += a
        elif s > 0:
            if s+a+1 >= 0:
                ans += s+a+1
                s = -1
            else:
                s += a
    return ans

b = A[0]
ans1 = count(b)
if b > 0:
    ans2 = count(-1)+b+1
elif b < 0:
    ans2 = count(1)+1-b

print(min(ans1, ans2))

Fixed submission:
N = int(input())
A = list(map(int, input().split()))

def count(s):
    ans = 0
    for i, a in enumerate(A):
        if i == 0:
            continue
        if s < 0:
            if 1-s-a >= 0:
                ans += 1-s-a
                s = 1
            else:
                s += a
        elif s > 0:
            if s+a+1 >= 0:
                ans += s+a+1
                s = -1
            else:
                s += a
    return ans

b = A[0]
ans1 = count(b)
if b > 0:
    ans2 = count(-1)+b+1
elif b < 0:
    ans2 = count(1)+1-b
else:
    ans1 = count(1)+1
    ans2 = count(-1)+1
print(min(ans1, ans2))
Buggy python submission (verdict: Time Limit Exceeded):
mod = 10**9+7

NN = 10**4 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, A, B, C, D = map(int, input().split())

Map = [[] for _ in range(N+1)]
for n in range(1, N+1):
    a = 1
    for _ in range(N+1):
        Map[n].append(a)
        a = a * g2[n] % mod

L = [[] for _ in range(N+1)]
for n in range(A, B+1):
    for c in range(C, D+1):
        if n*c > N:
            continue
        L[n].append(c)

dp = [0]*(N+1)
dp[0] = 1
for n in range(1, N+1):
    for i, c in enumerate(L[n]):
        if i == 0:
            dp2 = dp[:]
        for nn in range(N+1-n*c):
            dp2[nn+n*c] = (dp2[nn+n*c] + dp[nn] * Map[n][c] % mod * Map[c][1] % mod) % mod
        if i == len(L[n])-1:
            dp = dp2

ans = dp[N] * g1[N] % mod
print(ans)


Fixed submission:
mod = 10**9+7

NN = 10**4 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, NN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, A, B, C, D = map(int, input().split())

Map = [[] for _ in range(N+1)]
for n in range(1, N+1):
    a = 1
    for _ in range(N+1):
        Map[n].append(a)
        a = a * g2[n] % mod

L = [[] for _ in range(N+1)]
for n in range(A, B+1):
    for c in range(C, D+1):
        if n*c > N:
            continue
        L[n].append(c)

dp = [0]*(N+1)
dp[0] = 1
for n in range(1, N+1):
    for i, c in enumerate(L[n]):
        if i == 0:
            dp2 = dp[:]
        for nn in range(N+1-n*c):
            dp2[nn+n*c] = (dp2[nn+n*c] + dp[nn] * Map[n][c] % mod * Map[c][1] % mod) % mod
        if i == len(L[n])-1:
            dp = dp2

ans = dp[N] * g1[N] % mod
print(ans)
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())
state = [list(map(str, input().split())) for _ in range(h)]

A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for h in range(H):
  for w in range(W):
    if state[h][w] == 'snuke':
      ans = A[w] + str(h+1)
print(ans)

Fixed submission:
H, W = map(int, input().split())
state = [list(map(str, input().split())) for _ in range(H)]

A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
for h in range(H):
  for w in range(W):
    if state[h][w] == 'snuke':
      ans = A[w] + str(h+1)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq as hp
from bisect import bisect_left

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

B = [0 for _ in range(N+1)]
for i, a in enumerate(A):
    B[a] = i+1

q = [0, N+1]
ans = 0
for n, b in enumerate(B):
    #print(q)
    if n == 0:
        continue
    im = bisect_left(q, b)
    L = q[im-1]
    R = q[im]
    #print(n, b, L, R)
    ans += (R-b)*(b-L)*n
    #print(ans)
    q.append(b)
    q.sort()

print(ans)

Fixed submission:
from operator import itemgetter
import sys
input = sys.stdin.readline

# 二部探索木の代わり
# max_Xが大きい場合、0を含む場合は座標圧縮する

class BITbisect():
    def __init__(self, max_X):
        self.max_X = max_X + 1
        self.bit = [0]*(self.max_X+1)

    # x番目にaを加える
    def add(self, x, a):
        while x <= self.max_X:
            self.bit[x] += a
            x += x & -x

    def insert(self, x):
        self.add(x, 1)

    def delete(self, x):
        self.add(x, -1)

    # xまでに出現している個数
    def query_sum(self, x):
        s = 0
        while x > 0:
            s += self.bit[x]
            x -= x & -x
        return s

    def exist(self, x):
        if self.query_sum(x) - self.query_sum(x-1) > 0:
            return True
        return False
    
    def count(self, x):
        return self.query_sum(x) - self.query_sum(x-1)

    # xより大きくてbitに入ってるもののうち最小のもの
    # O((logN)^2)
    def upper(self, x):
        qx = self.query_sum(x) + 1
        if qx > self.query_sum(self.max_X):
            return False
        l = 0
        r = self.max_X
        while l < r:
            m = (l+r)//2
            if self.query_sum(m) < qx:
                if l == m:
                    return r
                l = m
            else:
                r = m
        if m == self.max_X:
            return False
        return m

    # x以下でbitに入っているもののうち最大のもの
    # O((logN)^2)
    def lower(self, x):
        qx = self.query_sum(x)
        if qx == 0:
            return False
        l = 0
        r = self.max_X
        while l < r:
            m = (l+r)//2
            if self.query_sum(m) < qx:
                if l == m:
                    return r
                l = m
            else:
                r = m
        return m

    # listみたいに表示
    def display(self):
        print('inside BIT:', end=' ')
        for x in range(1, self.max_X):
            if bit.exist(x):
                c = bit.count(x)
                for _ in range(c):
                    print(x, end=' ')
        print()


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

B = []
for i, a in enumerate(A):
    B.append((i+1, a))
B.sort(key=itemgetter(1))

bit = BITbisect(N)

ans = 0
for i, a in B:
    l = bit.lower(i)
    r = bit.upper(i)
    if l is False:
        l = 0
    if r is False:
        r = N+1
    ans += (i-l)*(r-i)*a
    bit.insert(i)
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())

alp = [chr(i) for i in range(97, 97+26)]

ans = ''
for s in S:
    loc = alp.index(s)
    if s == 'a': continue
    if loc + K >= 26:
        K -= 26 - loc
        ans += 'a'
    else:
        ans += s
if K > 0:
    K %= 26
    ans = ans[:-1] + alp[(alp.index(ans[-1])+K)%26]
print(ans)

Fixed submission:
S = input()
K = int(input())

alp = [chr(i) for i in range(97, 97+26)]

ans = ''
for s in S:
    loc = alp.index(s)
    if s == 'a' or loc + K < 26:
        ans += s
    else:
        K -= 26 - loc
        ans += 'a'

if K > 0:
    K %= 26
    ans = ans[:-1] + alp[(alp.index(ans[-1])+K)%26]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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

dp = [[None for _ in range(N)] for _ in range(N)]
for i in range(N):
    dp[0][i] = A[i]

ans = sum(dp[0])
for d in range(1, N):
    for i in range(N):
        dp[d][i] = min(dp[d-1][i], A[(i+d)%N])
    ans = min(ans, sum(dp[d])+X*d)

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

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

dp = [[None for _ in range(N)] for _ in range(N)]
for i in range(N):
    dp[0][i] = A[i]

ans = sum(dp[0])
for d in range(1, N):
    for i in range(N):
        dp[d][i] = min(dp[d-1][i], A[(i+d)%N])
    ans = min(ans, sum(dp[d])+X*d)

print(ans)
Buggy python submission (verdict: Runtime Error):
import math

N = int(input())
S = int(input())
L = N-S

def search(b, n=N):
    ans = 0
    while n >= b:
        ans += n%b
        n //= b
    ans += n
    return ans
s
if L < 0:
    print(-1)
elif L == 0:
    print(1)
else:
    P = []
    for l in range(1, int(math.sqrt(L))+1):
        if L%l == 0:
            P.append(l+1)
            P.append(L//l+1)
    P.sort()

    ans = -1
    for p in P:
        S0 = search(p)
        if S == S0:
            ans = p
            break

    print(ans)

Fixed submission:
import math

N = int(input())
S = int(input())
L = N-S

def search(b, n=N):
    ans = 0
    while n >= b:
        ans += n%b
        n //= b
    ans += n
    return ans


def main():

    if L < 0:
        print(-1)
    elif L == 0:
        print(N+1)
    else:
        P = []
        for l in range(1, int(math.sqrt(L))+2):
            if L%l == 0:
                P.append(l+1)
                P.append(L//l+1)
        P.sort()

        ans = -1
        for p in P:
            if p == 1: continue
            S0 = search(p)
            if S == S0:
                ans = p
                break

        print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

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

n, q = na()
a = na()
lasts = [-1] * (n+1)
rs = []
for i in range(n):
    if lasts[a[i]] != -1:
        rs.append((lasts[a[i]], i))
    lasts[a[i]] = i

rs.sort(key=lambda k: k[0])

qs = []
for i in range(q):
    u = na()
    qs.append((u[0]-1, u[1]-1, i))
qs.sort(key=lambda k: k[0])

def addfenwick(ft, i, v):
    if v == 0 or i < 0: return
    i += 1
    while i < len(ft):
        ft[i] += v
        i += i&-i

def sumfenwick(ft, i):
    s = 0
    i += 1
    while i > 0:
        s += ft[i]
        i -= i&-i
    return s

ft = [0] * (n+10)
anss = [0] * q
p = len(rs)-1
for q in qs[::-1]:
    while p >= 0 and rs[p][0] >= q[0]:
        addfenwick(ft, rs[p][1], 1)
        p -= 1
    anss[q[2]] = q[1]-q[0]+1-sumfenwick(ft, q[1])

for v in anss:
    print(v)


Fixed submission:
import sys
from operator import itemgetter

sys.setrecursionlimit(500005)
stdin = sys.stdin

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

n, q = na()
a = na()
lasts = [-1] * (n+1)
rs = []
for i in range(n):
    if lasts[a[i]] != -1:
        rs.append((lasts[a[i]], i))
    lasts[a[i]] = i

rs.sort(key=itemgetter(0))

qs = []
for i in range(q):
    u = na()
    qs.append((u[0]-1, u[1]-1, i))
qs.sort(key=itemgetter(0))

def addfenwick(ft, i, v):
    if v == 0 or i < 0: return
    i += 1
    while i < len(ft):
        ft[i] += v
        i += i&-i

def sumfenwick(ft, i):
    s = 0
    i += 1
    while i > 0:
        s += ft[i]
        i -= i&-i
    return s

ft = [0] * (n+10)
anss = [0] * q
p = len(rs)-1
for q in qs[::-1]:
    while p >= 0 and rs[p][0] >= q[0]:
        addfenwick(ft, rs[p][1], 1)
        p -= 1
    anss[q[2]] = q[1]-q[0]+1-sumfenwick(ft, q[1])

for v in anss:
    print(v)
Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

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

n = ni()
dic = defaultdict(int)
for i in range(n):
    dic[ns()] += 1
for w in ("AC", "WA", "TLE", "RE"):
    print(f"{w} x {dic[w]}")


Fixed submission:
import sys
from collections import defaultdict

sys.setrecursionlimit(500005)
stdin = sys.stdin

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

n = ni()
dic = defaultdict(int)
for i in range(n):
    dic[ns()] += 1
for w in ("AC", "WA", "TLE", "RE"):
    print(f"{w} x {dic[w]}")
Buggy python submission (verdict: Runtime Error):
import sys

stdin = sys.stdin

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

K = ni() - 1

for le in range(1, 11):
    for h in range(1, 10):
        for a in itertools.product((-1, 0, 1), repeat=le-1):
            cur = h
            ok = True
            for u in a:
                cur += u
                if cur > 9 or cur < 0:
                    ok = False
                    break
            if ok:
                if K == 0:
                    ret = [h] + [_ + h for _ in itertools.accumulate(a)]
                    print("".join(map(str, ret)))
                    sys.exit(0)
                K -= 1

Fixed submission:
import sys
import itertools

stdin = sys.stdin

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

K = ni() - 1

for le in range(1, 11):
    for h in range(1, 10):
        for a in itertools.product((-1, 0, 1), repeat=le-1):
            cur = h
            ok = True
            for u in a:
                cur += u
                if cur > 9 or cur < 0:
                    ok = False
                    break
            if ok:
                if K == 0:
                    ret = [h] + [_ + h for _ in itertools.accumulate(a)]
                    print("".join(map(str, ret)))
                    sys.exit(0)
                K -= 1
Buggy python submission (verdict: Time Limit Exceeded):
import sys

stdin = sys.stdin

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

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

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

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

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


Fixed submission:
import sys

stdin = sys.stdin

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

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

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

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

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