Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, C = map(int, input().split())
T = [[0 for k in range(100000)] for l in range(C)]

for k in range(N):
    s, t, c = map(int, input().split())
    T[c-1][s-1] += 1
    T[c-1][t] -= 1
for l in range(C):
    for k in range(1,100000):
        T[l][k] += T[l][k-1]

ans = 0
for k in range(100000):
    t = 0
    for l in range(C):
        if T[l][k]:
            t += 1
    ans = max(ans, t)

print(ans)


Fixed submission:
N, C = map(int, input().split())
T = [[0 for k in range(100001)] for l in range(C)]

for k in range(N):
    s, t, c = map(int, input().split())
    T[c-1][s-1] += 1
    T[c-1][t] -= 1
for l in range(C):
    for k in range(1,100001):
        T[l][k] += T[l][k-1]

ans = 0
for k in range(100001):
    t = 0
    for l in range(C):
        if T[l][k] >= 1:
            t += 1
    ans = max(ans, t)

print(ans)

Buggy python submission (verdict: Runtime Error):
N, C = map(int, input().split())
T = [[0 for k in range(100000)] for k in range(C)]

for k in range(N):
    s, t, c = map(int, input().split())
    T[c-1][s-1] += 1
    T[c-1][t] -= 1
for l in range(C):
    for k in range(1,100000):
        T[l][k] += T[l][k-1]

ans = 0
for k in range(100000):
    t = 0
    for l in range(C):
        if T[l][k]:
            t += 1
    ans = max(ans, t)

print(ans)


Fixed submission:
N, C = map(int, input().split())
T = [[0 for k in range(100001)] for l in range(C)]

for k in range(N):
    s, t, c = map(int, input().split())
    T[c-1][s-1] += 1
    T[c-1][t] -= 1
for l in range(C):
    for k in range(1,100001):
        T[l][k] += T[l][k-1]

ans = 0
for k in range(100001):
    t = 0
    for l in range(C):
        if T[l][k] >= 1:
            t += 1
    ans = max(ans, t)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# ABC 073 D
import itertools

N, M, R = map(int,input().split())
s = list(map(int,input().split()))
D = [[10**9+7 for k in range(N)] for l in range(N)]
for k in range(N):
    D[k][k] = 0
for k in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    D[A][B] = C
    D[B][A] = C

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[q][r] = min(D[q][r], D[q][p]+D[p][r])

cities = list(itertools.permutations(s))
ans = 10**9+7
for p in cities:
    t = 0
    for k in range(R-1):
        t += D[p[k]-1][p[k+1]-1]
    ans = min(ans,t)

print(ans)

Fixed submission:
# ABC 073 D
import itertools

N, M, R = map(int,input().split())
s = list(map(int,input().split()))
D = [[10**9+7 for k in range(N)] for l in range(N)]
for k in range(N):
    D[k][k] = 0
for k in range(M):
    A, B, C = map(int,input().split())
    A -= 1
    B -= 1
    D[A][B] = C
    D[B][A] = C

for p in range(N):
    for q in range(N):
        for r in range(N):
            D[q][r] = min(D[q][r], D[q][p]+D[p][r])

cities = list(itertools.permutations(s))
ans = 10**9+7
for p in cities:
    t = 0
    for k in range(R-1):
        t += D[p[k]-1][p[k+1]-1]
    ans = min(ans,t)

print(ans)
Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
    if a<b:
        t = a
        a = b
        b = t
    if b == 0:
        return a
    t = b
    b = a%b
    a = t
    return gcd(a,b)

def lcm(a,b):
    return a*b/gcd(a,b)

N = int(input())
ans = int(input())
for k in range(N-1):
    ans = int(lcm(ans, int(input())))

print(ans)


Fixed submission:
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

def lcm(a,b):
    return a*b//gcd(a,b)

N = int(input())
ans = 1
for k in range(N):
    ans = lcm(ans, int(input()))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(200010)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = list(map(int,input().split()))
    G = [[] for k in range(N)]
    for i in range(M):
        A, B = list(map(int,input().split()))
        G[A-1].append(B-1)
        G[B-1].append(A-1)
    for e in G[0]:
        if e in G[N-1]:
            print("POSSIBLE")
            exit(0)
    print("IMPOSSIBLE")
if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    N, M = map(int,input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int,input().split())
        G[a-1].append(b-1)
    for e in G[0]:
        if N-1 in G[e]:
            print("POSSIBLE")
            exit(0)
    print("IMPOSSIBLE")

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(200010)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = list(map(int,input().split()))
    G = [[] for k in range(N)]
    for i in range(M):
        A, B = list(map(int,input().split()))
        G[A-1].append(B-1)
        G[B-1].append(A-1)
    for e in G[0]:
        if e in G[N-1]:
            print("POSSIBLE")
            exit(0)
    print("IMPOSSIBLE")
if __name__ == '__main__':
    main()


Fixed submission:
import sys
def input():
    return sys.stdin.readline()[:-1]
def main():
    N, M = map(int,input().split())
    G = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int,input().split())
        G[a-1].append(b-1)
    for e in G[0]:
        if N-1 in G[e]:
            print("POSSIBLE")
            exit(0)
    print("IMPOSSIBLE")

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
import math
N, K = map(int,input().split())
A = sorted(list(map(int,input().split())))

if K in A:
    print("POSSIBLE")
    exit(0)
if K > max(A) or N == 1:
    print("IMPOSSIBLE")
    exit(0)

t = abs(A[1]-A[0])
if K%t==0:
    print("POSSIBLE")
    exit(0)

g = 1000000000
for k in range(1,N):
    g = min(g,math.gcd(A[k-1],A[k]))

if K%g == 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

if K in A:
    print("POSSIBLE")
    exit(0)
if K > max(A) or N == 1:
    print("IMPOSSIBLE")
    exit(0)

g = 1000000000
for k in range(1,N):
    g = min(g,gcd(A[k-1],A[k]))

if K%g == 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
# ABC 067 D
import sys
sys.setrecursionlimit(100000)

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

kyori1 = [100000 for k in range(N+1)]
kyori2 = [100000 for k in range(N+1)]

def dfs1(now, dist):
    for tsugi in G[now]:
        if kyori1[tsugi] == 100000:
            kyori1[tsugi] = dist + 1
            dfs1(tsugi, dist+1)

def dfs2(now, dist):
    for tsugi in G[now]:
        if kyori2[tsugi] == 100000:
            kyori2[tsugi] = dist + 1
            dfs2(tsugi, dist+1)

kyori1[1] = 0
dfs1(1,0)

kyori2[N] = 0
dfs2(N,0)

s = 0
f = 0
for k in range(1,N+1):
    if kyori1[k] <= kyori2[k]:
        f += 1
    else:
        s += 1

print("Fennec" if f > s else "Snuke")


Fixed submission:
# ABC 067 D
import sys
sys.setrecursionlimit(200000)

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

kyori1 = [100000 for k in range(N+1)]
kyori2 = [100000 for k in range(N+1)]

def dfs1(now, dist):
    for tsugi in G[now]:
        if kyori1[tsugi] == 100000:
            kyori1[tsugi] = dist + 1
            dfs1(tsugi, dist+1)

def dfs2(now, dist):
    for tsugi in G[now]:
        if kyori2[tsugi] == 100000:
            kyori2[tsugi] = dist + 1
            dfs2(tsugi, dist+1)

kyori1[1] = 0
dfs1(1,0)

kyori2[N] = 0
dfs2(N,0)

s = 0
f = 0
for k in range(1,N+1):
    if kyori1[k] <= kyori2[k]:
        f += 1
    else:
        s += 1

print("Fennec" if f > s else "Snuke")

Buggy python submission (verdict: Runtime Error):
# ABC 067 D
N = int(input())
G = [[] for k in range(N+1)]
for k in range(N-1):
    a, b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)

kyori1 = [100000 for k in range(N+1)]
kyori2 = [100000 for k in range(N+1)]

def dfs1(now, dist):
    for tsugi in G[now]:
        if kyori1[tsugi] == 100000:
            kyori1[tsugi] = dist + 1
            dfs1(tsugi, dist+1)

def dfs2(now, dist):
    for tsugi in G[now]:
        if kyori2[tsugi] == 100000:
            kyori2[tsugi] = dist + 1
            dfs2(tsugi, dist+1)

kyori1[1] = 0
dfs1(1,0)

kyori2[N] = 0
dfs2(N,0)

s = 0
f = 0
for k in range(1,N+1):
    if kyori1[k] <= kyori2[k]:
        f += 1
    else:
        s += 1

print("Fennec" if f > s else "Snuke")


Fixed submission:
# ABC 067 D
import sys
sys.setrecursionlimit(200000)

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

kyori1 = [100000 for k in range(N+1)]
kyori2 = [100000 for k in range(N+1)]

def dfs1(now, dist):
    for tsugi in G[now]:
        if kyori1[tsugi] == 100000:
            kyori1[tsugi] = dist + 1
            dfs1(tsugi, dist+1)

def dfs2(now, dist):
    for tsugi in G[now]:
        if kyori2[tsugi] == 100000:
            kyori2[tsugi] = dist + 1
            dfs2(tsugi, dist+1)

kyori1[1] = 0
dfs1(1,0)

kyori2[N] = 0
dfs2(N,0)

s = 0
f = 0
for k in range(1,N+1):
    if kyori1[k] <= kyori2[k]:
        f += 1
    else:
        s += 1

print("Fennec" if f > s else "Snuke")
Buggy python submission (verdict: Runtime Error):
from collections import Counter
N = int(input())
W = [Counter(input()) for k in range(N)]
A = [100000]*26
S = "abcdefghijklmnopqrstuvwxyz"
for e in W:
    for s in S:
        A[ord(s)-97] = min(A[ord(s)-97],e[s])
ans = ""
for k in range(N):
    ans += S[k]*A[k]
print(ans)


Fixed submission:
N = int(input())
S = [input() for k in range(N)]
A = "abcdefghijklmnopqrstuvwxyz"
C = [[0 for k in range(26)] for l in range(N)]

for k in range(N):
    for u in S[k]:
        C[k][A.find(u)] += 1

ans = ""
for p in range(26):
    t = 100
    for q in range(N):
        t = min(t,C[q][p])
    ans += A[p]*t
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
s = 0
e = 0
ans = 0
for k in range(len(S)-1):
    if S[k]=="A":
        s = k
        e = k+1
        for l in range(k+1,len(S)):
            if S[l]=="Z":
                e = max(e,l)
    ans = max(ans,e-s+1)
print(ans)


Fixed submission:
S = input()
s = S.index("A")
e = len(S)-S[::-1].index("Z")
print(e-s)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [list(map(int,input().split())) for k in range(N)]

ans = 0
for k in range(N):
    A[N-1-k][0] += ans
    while A[N-1-k][0]%A[N-1-k][1]!=0:
        A[N-1-k][0] += 1
        ans += 1

print(ans)

Fixed submission:
N = int(input())
A = [list(map(int,input().split())) for k in range(N)]

ans = 0
for k in range(N):
    A[N-1-k][0] += ans
    if A[N-1-k][0]%A[N-1-k][1]!=0:
        d = A[N-1-k][1]*(1+A[N-1-k][0]//A[N-1-k][1])-A[N-1-k][0]
        ans += d
        A[N-1-k][0] += d

print(ans)
Buggy python submission (verdict: Runtime Error):
# ABC 051 D
INF = 7+10**9
N, M = map(int,input().split())
P = []
D = [[INF for k in range(N)] for l in range(N)]
for k in range(N):
    D[k][k] = 0
for k in range(M):
    a, b, c = map(int,input().split())
    P.append([a-1,b-1,c])
    D[a-1][b-1] = c
    D[b-1][a-1] = c

# Floyd-Warshall
for k in range(M):
    for l in range(M):
        for m in range(M):
            D[l][m] = min(D[l][m], D[l][k]+D[k][m])

ans = M
for p in P:
    a, b, c = p[0], p[1], p[2]
    for k in range(N):
        if D[a][k] + c == D[b][k]:
            ans -= 1
            break 
print(ans)


Fixed submission:
# ABC 051 D
INF = 7+10**9
N, M = map(int,input().split())
P = []
D = [[INF for k in range(N)] for l in range(N)]
for k in range(N):
    D[k][k] = 0
for k in range(M):
    a, b, c = map(int,input().split())
    P.append([a-1,b-1,c])
    D[a-1][b-1] = c
    D[b-1][a-1] = c

# Floyd-Warshall
for k in range(N):
    for l in range(N):
        for m in range(N):
            D[l][m] = min(D[l][m], D[l][k]+D[k][m])

ans = M
for p in P:
    a, b, c = p[0], p[1], p[2]
    for k in range(N):
        if D[a][k] + c == D[b][k]:
            ans -= 1
            break 
print(ans)
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())
S = [input().split() for k in range(H)]
A = "ABCDEFGHIJ"

for k in range(H):
    for l in range(W):
        if S[k][l]=="snuke":
            print("".join([A[l],str(k+1)]))
            exit(0)

Fixed submission:
H, W = map(int, input().split())
S = [input().split() for k in range(H)]
A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

for k in range(H):
    for l in range(W):
        if S[k][l]=="snuke":
            print("".join([A[l],str(k+1)]))
            exit(0)
Buggy python submission (verdict: Time Limit Exceeded):
N, x = map(int,input().split())
A = list(map(int,input().split()))

ans = sum(A)
A = A+A

for k in range(1,N):
    L = [0]*N
    for l in range(N):
        T = A[N+l-k:N+l+1]
        L[l] = min(T)
    ans = min(ans,sum(L)+k*x)

print(ans)


Fixed submission:
# AGC 004 B
N, x = map(int,input().split())
A = list(map(int,input().split()))

M = [[float("inf")]*N for k in range(N)]
for k in range(N):
    M[0][k] = A[k]

for k in range(N):
    for l in range(N):
        M[k][l] = min(M[k-1][l],A[k-l])

ans = sum(A)
for k in range(1,N):
    ans = min(ans,sum(M[k])+x*k)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, x = map(int,input().split())
A = list(map(int,input().split()))

ans = sum(A)
A = A+A

for k in range(1,N):
    L = [0]*N
    for l in range(N):
        T = A[N+l-k:N+l+1]
        L[l] = min(T)
    ans = min(ans,sum(L)+k*x)

print(ans)


Fixed submission:
# AGC 004 B
N, x = map(int,input().split())
A = list(map(int,input().split()))

M = [[float("inf")]*N for k in range(N)]
for k in range(N):
    M[0][k] = A[k]

for k in range(N):
    for l in range(N):
        M[k][l] = min(M[k-1][l],A[k-l])

ans = sum(A)
for k in range(1,N):
    ans = min(ans,sum(M[k])+x*k)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, A = map(int,input().split())
x = list(map(int,input().split()))

dp = [[[0 for k in range(N*A+1)] for j in range(N+1)] for l in range(N+1)]
dp[0][0][0] = 1

for p in range(N):
    for q in range(N):
        for r in range(N*A):
            dp[p+1][q][r] += dp[p][q][r]
            if r+x[p] <= N*A:
                dp[p+1][q+1][r+x[p]] += dp[p][q][r]
                
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)

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

dp = [[[0 for k in range(N*A+1)] for j in range(N+1)] for l in range(N+1)]
dp[0][0][0] = 1

for p in range(N):
    for q in range(N):
        for r in range(N*A):
            dp[p+1][q][r] += dp[p][q][r]
            if r+x[p] <= N*A:
                dp[p+1][q+1][r+x[p]] += dp[p][q][r]
                
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, A = map(int,input().split())
x = list(map(int,input().split()))

dp = [[[0]*(max(sum(x),N*A)+1) for k in range(N+1)] for l in range(N+1)]
# dp[i][j][k] := i番目まででj枚選んで和がkになる組み合わせの数
dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(sum(x)+1):
            dp[i+1][j][k] += dp[i][j][k]
            if k-x[i] >= 0:
                dp[i+1][j+1][k] += dp[i][j][k-x[i]]

ans = 0
for k in range(1,N+1):
    ans += dp[N][k][A*k]
print(ans)


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

dp = [[[0]*(max(sum(x),N*A)+1) for k in range(N+1)] for l in range(N+1)]
# dp[i][j][k] := i番目まででj枚選んで和がkになる組み合わせの数
dp[0][0][0] = 1

for i in range(N):
    for j in range(N):
        for k in range(sum(x)+1):
            dp[i+1][j][k] += dp[i][j][k]
            if k-x[i] >= 0:
                dp[i+1][j+1][k] += dp[i][j][k-x[i]]

ans = 0
for k in range(1,N+1):
    ans += dp[N][k][A*k]
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter
import heapq

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

cur = n-1
bit = 1
for i in range(n):
    if a[i] == b[i]:
        while a[i]==b[cur]:
            cur-=bit
            if cur == 0:
                bit = -1
            if bit == -1 and cur == n-1:
                print('No')
                exit(0)
        b[i], b[cur] = b[cur], b[i]
print('Yes')
print(' '.join(list(map(str, b))))
    
    


Fixed submission:
from collections import Counter
import heapq

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

cur = n-1
bit = 1
for i in range(n):
    if a[i] == b[i]:
        while a[i]==b[cur] or a[cur]==b[i]:
            if cur == 0:
                bit = -1
            if bit == -1 and cur == n-1:
                print('No')
                exit(0)
            cur-=bit
        b[i], b[cur] = b[cur], b[i]
print('Yes')
print(' '.join(list(map(str, b))))
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
H, W, M = map(int, input().split())
bomb = []
for i in range(M):
    h, w = map(int, input().split())
    h-=1; w-=1
    bomb.append((h, w))

row = [0] * H
col = [0] * W

for h, w in bomb:
    row[h] += 1
    col[w] += 1

lmax = max(row) + max(col)
row = [(r, i) for i, r in enumerate(row)]
col = [(c, i) for i, c in enumerate(col)]
bomb = set(bomb)

for r, i in row:
    for c, j in col:
        if r+c < lmax: continue
        if not (i, j) in bomb:
            print(lmax)
            exit()
print(lmax-1)

        





Fixed submission:
import heapq
H, W, M = map(int, input().split())
bomb = []
for i in range(M):
    h, w = map(int, input().split())
    h-=1; w-=1
    bomb.append((h, w))

row = [0] * H
col = [0] * W

for h, w in bomb:
    row[h] += 1
    col[w] += 1

lmax = max(row) + max(col)
row = [(r, i) for i, r in enumerate(row)]
col = [(c, i) for i, c in enumerate(col)]
row.sort(reverse=True)
col.sort(reverse=True)
bomb = set(bomb)

for r, i in row:
    for c, j in col:
        if r+c < lmax: break
        if not (i, j) in bomb:
            print(lmax)
            exit()
print(lmax-1)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq
H, W, M = map(int, input().split())
bomb = []
for i in range(M):
    h, w = map(int, input().split())
    h-=1; w-=1
    bomb.append((h, w))

row = [0] * H
col = [0] * W

for h, w in bomb:
    row[h] += 1
    col[w] += 1

lmax = max(row) + max(col)
row = [(r, i) for i, r in enumerate(row)]
col = [(c, i) for i, c in enumerate(col)]
bomb = set(bomb)

for r, i in row:
    for c, j in col:
        if r+c < lmax: continue
        if not (i, j) in bomb:
            print(lmax)
            exit()
print(lmax-1)

        





Fixed submission:
import heapq
H, W, M = map(int, input().split())
bomb = []
for i in range(M):
    h, w = map(int, input().split())
    h-=1; w-=1
    bomb.append((h, w))

row = [0] * H
col = [0] * W

for h, w in bomb:
    row[h] += 1
    col[w] += 1

lmax = max(row) + max(col)
row = [(r, i) for i, r in enumerate(row)]
col = [(c, i) for i, c in enumerate(col)]
row.sort(reverse=True)
col.sort(reverse=True)
bomb = set(bomb)

for r, i in row:
    for c, j in col:
        if r+c < lmax: break
        if not (i, j) in bomb:
            print(lmax)
            exit()
print(lmax-1)
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))
p = [_p-1 for _p in p]
c = list(map(int, input().split()))

ans = -float('inf')

visited = [False] * n
ss = []
for i in range(n):
    if visited[i]: continue
    cur = i
    s = []
    while not visited[cur]:
        visited[cur] = True
        s.append(c[cur])
        cur = p[cur]
    ss.append(s)

for s in ss:
    m = len(s)
    cumsum = [0] * (m*2+1)
    for i in range(2*m):
        cumsum[i+1] = cumsum[i] + s[i%m]
    
    amari = [-float('inf')] * m
    for i in range(m):
        for j in range(m):
            amari[j] = max(amari[j], cumsum[i+j] - cumsum[i])
    
    for r in range(0, m):
        if r > k: continue
        q = (k-r)//m
        if r==0 and q==0:
            continue
        
        if cumsum[m] > 0:
            ans = max(ans, amari[r] + cumsum[m]*q)
        elif r > 0:
            ans = max(ans, amari[r])

print(ans)


Fixed submission:
n, k = map(int, input().split())
p = list(map(int, input().split()))
p = [_p-1 for _p in p]
c = list(map(int, input().split()))

ans = -float('inf')

visited = [False] * n
ss = []
for i in range(n):
    if visited[i]: continue
    cur = i
    s = []
    while not visited[cur]:
        visited[cur] = True
        s.append(c[cur])
        cur = p[cur]
    ss.append(s)

for s in ss:
    m = len(s)
    cumsum = [0] * (m*2+1)
    for i in range(2*m):
        cumsum[i+1] = cumsum[i] + s[i%m]
    
    amari = [-float('inf')] * m
    for i in range(m):
        for j in range(m):
            amari[j] = max(amari[j], cumsum[i+j] - cumsum[i])
    
    for r in range(0, m):
        if r > k: continue
        q = (k-r)//m
        if r==0 and q==0:
            continue
        
        if cumsum[m] > 0:
            ans = max(ans, amari[r] + cumsum[m]*q)
        elif r > 0:
            ans = max(ans, amari[r])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
r, c, k = map(int, input().split())
rcv = [list(map(int, input().split())) for i in range(k)]

area = [[0] * (c+1) for i in range(r+1)]
for a, b, v in rcv:
    area[a-1][b-1] = v

# dp[i][j][k]: その行でiまで拾っており、
# j行k列目に到達時点の最大スコア
dp = [[[-1] * (c+1) for i in range(r+1)] for j in range(4)]
dp[0][0][0] = 0

for rr in range(r+1):
    for cc in range(c+1):
        for i in range(4):
            # 取って右
            if i+1<4 and cc<c and area[rr][cc]>0:
                dp[i+1][rr][cc+1] = max(dp[i+1][rr][cc+1],
                                        dp[i][rr][cc]+area[rr][cc])
            # 取って下
            if i+1<4 and rr<r and area[rr][cc]>0:
                dp[0][rr+1][cc] = max(dp[0][rr+1][cc],
                                      dp[i][rr][cc]+area[rr][cc])
            # 取らずに右
            if cc<c:
                dp[i][rr][cc+1] = max(dp[i][rr][cc+1],
                                      dp[i][rr][cc])
            # 取らずに下
            if rr<r:
                dp[0][rr+1][cc] = max(dp[0][rr+1][cc],
                                      dp[i][rr][cc])
# ans: r行c列目の最大値（iは問わず）
ans = max([dp[i][r][c] for i in range(4)])
print(ans)





Fixed submission:
r, c, k = map(int, input().split())
rcv = [list(map(int, input().split())) for i in range(k)]

area = [[0] * (c+1) for i in range(r+1)]
for a, b, v in rcv:
    area[a-1][b-1] = v

# dp[i][j][k]: その行でiまで拾っており、
# j行k列目に到達時点の最大スコア
dp = [[[-1] * (c+1) for i in range(r+1)] for j in range(4)]
dp[0][0][0] = 0

for rr in range(r+1):
    for cc in range(c+1):
        for i in range(4):
            # 取って右
            if i+1<4 and cc<c and area[rr][cc]>0:
                dp[i+1][rr][cc+1] = max(dp[i+1][rr][cc+1],
                                        dp[i][rr][cc]+area[rr][cc])
            # 取って下
            if i+1<4 and rr<r and area[rr][cc]>0:
                dp[0][rr+1][cc] = max(dp[0][rr+1][cc],
                                      dp[i][rr][cc]+area[rr][cc])
            # 取らずに右
            if cc<c:
                dp[i][rr][cc+1] = max(dp[i][rr][cc+1],
                                      dp[i][rr][cc])
            # 取らずに下
            if rr<r:
                dp[0][rr+1][cc] = max(dp[0][rr+1][cc],
                                      dp[i][rr][cc])
# ans: r行c列目の最大値（iは問わず）
ans = max([dp[i][r][c] for i in range(4)])
print(ans)