Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = []
count = 0
for i in range(N):
    a += [''.join(sorted(input()))]
sorted_a = sorted(a)
for i in range(N-1):
    for j in range(1, N):
        if i+j >= N:
            break
        if sorted_a[i] == sorted_a[i+j]:
            count += 1
        else:
            break
print(count)

Fixed submission:
from collections import defaultdict

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

d = defaultdict(int)
for i in range(n):
    d["".join(sorted(s[i]))] += 1

ans = 0
for k in d.keys():
    ans += d[k] * (d[k]-1) // 2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
N = int(input())
a = []
count = 0
for i in range(N):
    a += [''.join(sorted(input()))]
sorted_a = sorted(a)
for i in range(N-1):
    for j in range(1, N):
        if i+j >= N:
            break
        if sorted_a[i] == sorted_a[i+j]:
            count += 1
        else:
            break
print(count)

Fixed submission:
from collections import defaultdict

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

d = defaultdict(int)
for i in range(n):
    d["".join(sorted(s[i]))] += 1

ans = 0
for k in d.keys():
    ans += d[k] * (d[k]-1) // 2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
N = int(input())
a = []
count = 0
for i in range(N):
    a += [''.join(sorted(input()))]
for i in range(N-1):
    for j in range(1, N):
        if i+j >= N:
            break
        if a[i] == a[i+j]:
            count += 1
print(count)

Fixed submission:
from collections import defaultdict

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

d = defaultdict(int)
for i in range(n):
    d["".join(sorted(s[i]))] += 1

ans = 0
for k in d.keys():
    ans += d[k] * (d[k]-1) // 2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
N = int(input())
a = []
count = 0
for i in range(N):
    a += [sorted(input())]
for i in range(N-1):
    for j in range(1, N):
        if i+j >= N:
            break
        if a[i] == a[i+j]:
            count += 1
print(count)

Fixed submission:
from collections import defaultdict

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

d = defaultdict(int)
for i in range(n):
    d["".join(sorted(s[i]))] += 1

ans = 0
for k in d.keys():
    ans += d[k] * (d[k]-1) // 2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
N = int(input())
a = []
count = 0
for i in range(N):
    a += [sorted(input())]
for i in range(N):
    for j in range(1, N):
        if i+j >= N:
            break
        if a[i] == a[i+j]:
            count += 1
print(count)

Fixed submission:
from collections import defaultdict

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

d = defaultdict(int)
for i in range(n):
    d["".join(sorted(s[i]))] += 1

ans = 0
for k in d.keys():
    ans += d[k] * (d[k]-1) // 2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

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

pay_list = []
heapq.heapify(pay_list)
ans = 0
for i in range(1, M+1):
    # 実行可能なバイトリストを抽出
    for j in range(len(AB)-1, -1, -1):
        a = AB[j][0]
        b = AB[j][1]
        if a <= i:
            # heappopで最大値を取り出したいため、補正値の(-1)を乗じておく
            heapq.heappush(pay_list, b*(-1))
            AB.pop(j)
    # 最大の報酬の値を取り出して足す
    if len(pay_list) > 0:
        ans += heapq.heappop(pay_list) * (-1)
print(ans)


Fixed submission:
import heapq

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

pay_list = []
heapq.heapify(pay_list)
ans = 0
# AB = sorted(AB, key=lambda x: x[0])
AB = sorted(AB, reverse=True)
for i in range(1, M+1):
    # 実行可能なバイトリストを抽出
    for j in range(len(AB)-1, -1, -1):
        a = AB[j][0]
        b = AB[j][1]
        if a <= i:
            # heappopで最大値を取り出したいため、補正値の(-1)を乗じておく
            heapq.heappush(pay_list, b*(-1))
            AB.pop(j)
        else:
            break
    # 最大の報酬の値を取り出して足す
    if len(pay_list) > 0:
        ans += heapq.heappop(pay_list) * (-1)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

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

pay_list = []
heapq.heapify(pay_list)
ans = 0
for i in range(1, M+1):
    # 実行可能なバイトリストを抽出
    for j in range(len(AB)-1, -1, -1):
        a = AB[j][0]
        b = AB[j][1]
        if a <= i:
            # heappopで最大値を取り出したいため、補正値の(-1)を乗じておく
            heapq.heappush(pay_list, b*(-1))
            AB.pop(j)
    # 最大の報酬の値を取り出して足す
    if len(pay_list) > 0:
        ans += heapq.heappop(pay_list) * (-1)
print(ans)


Fixed submission:
import heapq

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

pay_list = []
heapq.heapify(pay_list)
ans = 0
# AB = sorted(AB, key=lambda x: x[0])
AB = sorted(AB, reverse=True)
for i in range(1, M+1):
    # 実行可能なバイトリストを抽出
    for j in range(len(AB)-1, -1, -1):
        a = AB[j][0]
        b = AB[j][1]
        if a <= i:
            # heappopで最大値を取り出したいため、補正値の(-1)を乗じておく
            heapq.heappush(pay_list, b*(-1))
            AB.pop(j)
        else:
            break
    # 最大の報酬の値を取り出して足す
    if len(pay_list) > 0:
        ans += heapq.heappop(pay_list) * (-1)
print(ans)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
N = int(input())
digit_count = len(str(N))
if digit_count == 1:
    print(N)
if (digit_count % 2 == 1):
    print(N - int(str(90) * (digit_count//2)))
else:
    total = 0
    for i in range(0, digit_count//2):
        total += 9*(100**i)
    print(total)

Fixed submission:
# -*- coding: utf-8 -*-
N = int(input())
digit_count = len(str(N))
if digit_count == 1:
    print(N)
elif (digit_count % 2 == 1):
    print(N - int(str(90) * (digit_count//2)))
else:
    total = 0
    for i in range(0, digit_count//2):
        total += 9*(100**i)
    print(total)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
N= int(input())
if N == 1:
# -*- coding: utf-8 -*-
N = int(input())
digit_count = len(str(N))
if digit_count == 1:
    print(N)
if (digit_count % 2 == 1):
    print(N - int(str(90) * (digit_count//2)))
else:
    total = 0
    for i in range(0, digit_count//2):
        total += 9*(100**i)
    print(total)

Fixed submission:
# -*- coding: utf-8 -*-
N = int(input())
digit_count = len(str(N))
if digit_count == 1:
    print(N)
elif (digit_count % 2 == 1):
    print(N - int(str(90) * (digit_count//2)))
else:
    total = 0
    for i in range(0, digit_count//2):
        total += 9*(100**i)
    print(total)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = []
for i in range(N):
    a.append(int(input()))
for i in range(N):
    temp = a[0:i] + a[i + 1:]
    print(max(temp))

Fixed submission:
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
max_A = max(A)
max_num = 0
for i in range(N):
    if A[i] == max_A:
        # 最大値が複数ある場合の計算削減
        max_num += 1
        if max_num > 1:
            print(max_A)
        else:
            print(max(A[:i] + A[i + 1:]))
    else:
        print(max_A)
Buggy python submission (verdict: Runtime Error):
import math

L, R = map(int, input().split())
ans = math.inf
for i in range(L, R+1):
    for j in range(i+1, R+1):
        ans = min(ans, i * j % 2019)
        if ans == 0:
            print(0)
            exit()
print(ans)

Fixed submission:
L, R = map(int, input().split())
ans = float('inf')
for i in range(L, R+1):
    for j in range(i+1, R+1):
        ans = min(ans, i * j % 2019)
        if ans == 0:
            print(0)
            exit()
print(ans)
Buggy python submission (verdict: Runtime Error):
S = int(input()).sort()
if S[0] == S[1] and S[2] == S[3] and S[0] != S[2]:
    print('YES')
else:
    print('NO')

Fixed submission:
S = sorted(list(input()))
if S[0] == S[1] and S[2] == S[3] and S[0] != S[2]:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
N, L = map(int, input().split())
p_list = []
for i in range(1, N+1):
    p_list += [L + i - 1]
print(sum(p_list) - sorted(p_list, key=abs)[0])

Fixed submission:
S = input()
tmp = S[0]
for num in S[1:]:
    if num == tmp:
        print('Bad')
        exit()
    tmp = num
print('Good')
Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
L = list(map(int, input().split()))
d = 0
for i in range(1, N + 2):
    d += L[i - 1]
    if d > X:
        print(i)
        exit()

Fixed submission:
N, X = map(int, input().split())
L = list(map(int, input().split()))
d = 0
if L[0] > X:
    print(0)
for i in range(1, N + 1):
    d += L[i - 1]
    if d > X:
        print(i)
        exit()
print(N + 1)
Buggy python submission (verdict: Runtime Error):
s = input()
rest = 15 - len(s)
if s.count('o') + rest > 7:
    print('YES')
else:
    print('NO'

Fixed submission:
s = input()
rest = 15 - len(s)
if s.count('o') + rest > 7:
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
ans = []
for i in range(m):
    res = []
    for j in range(lr[i][0], lr[i][1] + 1):
        res.append(j)
    if i == 0:
        ans = set(res)
    else:
        ans = set(ans) & set(res)
print(len(ans))


Fixed submission:
n, m = map(int, input().split())
mi, ma = 1, n
for _ in range(m):
    l, r = map(int, input().split())
    mi = max(l, mi)
    ma = min(r, ma)
print(max(0, ma - mi + 1))
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
bc = [list(map(int, input().split())) for _ in range(m)]
for b, c in bc:
    for _ in range(b):
        x = heapq.heappop(a)
        if c > x:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, x)
print(sum(a))


Fixed submission:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, key=lambda x: -x[1])
for b, c in bc:
    for _ in range(b):
        x = heapq.heappop(a)
        if c > x:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, x)
            break
print(sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]
for i in range(m):
    a += bc[i][0] * [bc[i][1]]
a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)
ans = 0
for i in range(n):
    ans += heapq.heappop(a)*(-1)
print(ans)


Fixed submission:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, key=lambda x: -x[1])
for b, c in bc:
    for _ in range(b):
        x = heapq.heappop(a)
        if c > x:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, x)
            break
print(sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]
for i in range(m):
    a += bc[i][0] * [bc[i][1]]
a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)
ans = []
for i in range(n):
    ans.append(heapq.heappop(a)*(-1))

print(sum(ans))

Fixed submission:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, key=lambda x: -x[1])
for b, c in bc:
    for _ in range(b):
        x = heapq.heappop(a)
        if c > x:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, x)
            break
print(sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]
for i in range(m):
    a += bc[i][0] * [bc[i][1]]
sorted_a = sorted(a, reverse=True)
print(sum(sorted_a[0:n]))

Fixed submission:
import heapq

n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
bc = [list(map(int, input().split())) for _ in range(m)]
bc = sorted(bc, key=lambda x: -x[1])
for b, c in bc:
    for _ in range(b):
        x = heapq.heappop(a)
        if c > x:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, x)
            break
print(sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        if r*i + g*j > n:
            break
        if (n - r*i - g*j) == 0 or ((n - r*i - g*j) >= b and (n - r*i - g*j) % b == 0):
            ans += 1
print(ans)

Fixed submission:
r, g, b, n = map(int, input().split())

ans = 0
for i in range(n//r+1):
    for j in range(n//g+1):
        if r*i + g*j > n:
            break
        if (n - r*i - g*j) == 0 or ((n - r*i - g*j) >= b and (n - r*i - g*j) % b == 0):
            ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
n = int(input())
a = list(map(int, input().split()))

ans = 1
# 1つ使わない中で最大公約数が最大のものを求める
for i in range(0, n):
    if i == 0:
        gcd_num = a[1]
    else:
        gcd_num = a[0]
    for j in range(1, n):
        if i == j:
            continue
        gcd_num = fractions.gcd(gcd_num, a[j])
    ans = max(ans, gcd_num)
print(ans)


Fixed submission:
import fractions
n = int(input())
a = [0] + list(map(int, input().split())) + [0]

# 前処理。left, rightでそれぞれ累積gcdを作っておく
left = [0] * (n + 2)
right = [0] * (n + 2)

for i in range(n):
    left[i] = fractions.gcd(left[i - 1], a[i])

for i in range(n, 0, -1):
    right[i] = fractions.gcd(right[i + 1], a[i])

for i in range(1, n):
    right[-i - 1] = fractions.gcd(right[-i], a[-i - 1])

ans = 1
for i in range(1, n + 1):
    ans = max(ans, fractions.gcd(left[i - 1], right[i + 1]))
print(ans)

Buggy python submission (verdict: Runtime Error):
import math
n = int(input())
a = list(map(int, input().split()))

ans = 1
# 1つ使わない中で最大公約数が最大のものを求める
for i in range(0, n):
    if i == 0:
        gcd_num = a[1]
    else:
        gcd_num = a[0]
    for j in range(1, n):
        if i == j:
            continue
        gcd_num = math.gcd(gcd_num, a[j])
    ans = max(ans, gcd_num)
print(ans)

Fixed submission:
import fractions
n = int(input())
a = [0] + list(map(int, input().split())) + [0]

# 前処理。left, rightでそれぞれ累積gcdを作っておく
left = [0] * (n + 2)
right = [0] * (n + 2)

for i in range(n):
    left[i] = fractions.gcd(left[i - 1], a[i])

for i in range(n, 0, -1):
    right[i] = fractions.gcd(right[i + 1], a[i])

for i in range(1, n):
    right[-i - 1] = fractions.gcd(right[-i], a[-i - 1])

ans = 1
for i in range(1, n + 1):
    ans = max(ans, fractions.gcd(left[i - 1], right[i + 1]))
print(ans)

Buggy python submission (verdict: Runtime Error):
import math
n = int(input())
a = list(map(int, input().split()))

ans = 1
gcd_num = a[0]
# 1つ使わない中で最大公約数が最大のものを求める
for i in range(0, n):
    if i == 0:
        gcd_num = a[1]
    else:
        gcd_num = a[0]
    for j in range(0, n):
        if i == j:
            continue
        gcd_num = math.gcd(gcd_num, a[j])
    ans = max(ans, gcd_num)
print(ans)

Fixed submission:
import fractions
n = int(input())
a = [0] + list(map(int, input().split())) + [0]

# 前処理。left, rightでそれぞれ累積gcdを作っておく
left = [0] * (n + 2)
right = [0] * (n + 2)

for i in range(n):
    left[i] = fractions.gcd(left[i - 1], a[i])

for i in range(n, 0, -1):
    right[i] = fractions.gcd(right[i + 1], a[i])

for i in range(1, n):
    right[-i - 1] = fractions.gcd(right[-i], a[-i - 1])

ans = 1
for i in range(1, n + 1):
    ans = max(ans, fractions.gcd(left[i - 1], right[i + 1]))
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
ACGT = ['A', 'C', 'G', 'T']
count = 0
max_count = 0
for w in S:
    if w in ACGT:
        count += 1
    else:
        if count > max_count:
            max_count += count
print(max_count

Fixed submission:
S = input()
ACGT = ['A', 'C', 'G', 'T']
count = 0
max_count = 0
for w in S:
    if w in ACGT:
        count += 1
    if count > max_count:
        max_count = count
    if w not in ACGT:
        count = 0
print(max_count)
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

index = []
for i in range(n-1):
    if s[i] + s[i+1] == 'AC':
        index.append(i)

for le, ri in lr:
    count = 0
    for a in index:
        if le-1 <= a and a + 1 <= ri - 1:
            count += 1
    print(count)

Fixed submission:
n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]
t = [0]
count = 0
for i in range(1, n):
    if s[i-1] + s[i] == 'AC':
        count += 1
    t.append(count)
for le, ri in lr:
    print(t[ri-1] - t[le-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A, B = [0] * N, [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())

total = 0
while len(A) > 0:
    i = A.index(min(A))
    if B[i] == M:
        total += A[i] * B[i]
        break
    elif B[i] > M:
        total += A[i] * M
        break
    else:
        total += A[i] * B[i]
        M -= B[i]
        A.pop(i)
        B.pop(i)
print(total)

Fixed submission:
N, M = map(int, input().split())
shop = []
for i in range(N):
    shop.append(list(map(int, input().split())))

shop.sort()

total = 0
for i in range(len(shop)):
    if shop[i][1] == M:
        total += shop[i][0] * shop[i][1]
        break
    elif shop[i][1] > M:
        total += shop[i][0] * M
        break
    else:
        total += shop[i][0] * shop[i][1]
        M -= shop[i][1]
print(total)
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input())
if b % a == 0:
    print(a + b)
else:
    print(b - a)


Fixed submission:
a, b = map(int, input().split())
if b % a == 0:
    print(a + b)
else:
    print(b - a)

Buggy python submission (verdict: Runtime Error):
a, b = map(int, input())
if a % b == 0:
    print(a + b)
else:
    print(b - a)

Fixed submission:
a, b = map(int, input().split())
if b % a == 0:
    print(a + b)
else:
    print(b - a)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

while len(a) >= 2:
    min_a = min(a)

    # 最小値が２つある場合に一回はskipする
    flag = False
    for i in range(len(a)):
        if a[i] == min_a and not flag:
            flag = True
            continue
        if flag or a[i] != min_a:
            a[i] = a[i] % min_a
    while True:
        if a.count(0) > 0:
            a.remove(0)
        else:
            break
print(a[0])


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


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

ans = a[0]
for i in range(1, len(a)):
    ans = gcd(ans, a[i])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

while len(a) >= 2:
    min_a = min(a)

    # 最小値が２つある場合に一回はskipする
    flag = False
    for i in range(len(a)):
        if a[i] == min_a and not flag:
            flag = True
            continue
        if flag or a[i] != min_a:
            a[i] = a[i] % min_a
    while True:
        if a.count(0) > 0:
            a.remove(0)
        else:
            break
print(a[0])


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


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

ans = a[0]
for i in range(1, len(a)):
    ans = gcd(ans, a[i])
print(ans)
Buggy python submission (verdict: Runtime Error):
k, a, b = map(int, input().split())

max_change = max(0, (k - (a - 1)) // 2)
print(max(k+1, 1+k-max_change*2 + (b-a)*max_change)

Fixed submission:
k, a, b = map(int, input().split())

max_change = max(0, (k - (a - 1)) // 2)
print(max(k+1, 1+k-max_change*2 + (b-a)*max_change))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n
for i in range(1, n):
    min_tmp = float('inf')
    for j in range(1, k+1):
        if j > i:
            break
        min_tmp = min(min_tmp, dp[i-j] + abs(h[i]-h[i-j]))
    dp[i] = min_tmp
print(dp[-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n
for i in range(1, n):
    min_tmp = float('inf')
    for j in range(1, k+1):
        if j > i:
            break
        min_tmp = min(min_tmp, dp[i-j] + abs(h[i]-h[i-j]))
    dp[i] = min_tmp
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n
for i in range(1, n):
    tmp = []
    for j in range(1, k + 1):
        if j > i:
            break
        tmp.append(dp[i-j] + abs(h[i]-h[i-j]))
    dp[i] = min(tmp)
print(dp[-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n
for i in range(1, n):
    min_tmp = float('inf')
    for j in range(1, k+1):
        if j > i:
            break
        min_tmp = min(min_tmp, dp[i-j] + abs(h[i]-h[i-j]))
    dp[i] = min_tmp
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

inf = float("inf")
dp = [[-inf for _ in range(W+1)] for _ in range(N+1)]
for i in range(W+1):
    dp[0][i] = 0

for i in range(N):
    weight = wv[i][0]
    value = wv[i][1]
    for w in range(W+1):
        # 重量に収まる場合のみ価値を加える
        if weight <= w:
            dp[i+1][w] = max(dp[i][w-weight] + value, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(max(dp[-1]))


Fixed submission:
# ナップザック問題
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

inf = float("inf")
dp = [[-inf for _ in range(W+1)] for _ in range(N+1)]
for i in range(W+1):
    dp[0][i] = 0

for i in range(N):
    weight = wv[i][0]
    value = wv[i][1]
    for w in range(W+1):
        # 重量に収まる場合のみ価値を加える
        if weight <= w:
            dp[i+1][w] = max(dp[i][w-weight] + value, dp[i][w])
        else:
            dp[i+1][w] = dp[i][w]
print(max(dp[-1]))
Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b


N, M = map(int, input().split())
S = input()
T = input()
x = gcd(N, M)
n = N // x
m = M // x

for i in range(3):
    if S[n*i] == T[m*i]:
        print(-1)
        break
print(N*M//x)


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


N, M = map(int, input().split())
S = input()
T = input()
x = gcd(N, M)
n = N // x
m = M // x

for i in range(x):
    if S[n*i] != T[m*i]:
        print(-1)
        exit()
print(N*M//x)
Buggy python submission (verdict: Runtime Error):
s = input()
k = int(input())
for i in len(s):
    if s[i] != '1' and i < k:
        print(s[i])
        exit()
print('1')

Fixed submission:
s = input()
k = int(input())
for i in range(len(s)):
    if s[i] != '1' and i < k:
        print(s[i])
        exit()
print('1')
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

min_count = float('inf')
for i in range(n):
    count = 0
    for j in range(n):
        if i == j:
            continue
        elif j < i and s[j] == 'W':
            count += 1
        elif j > i and s[j] == 'E':
            count += 1
    min_count = min(min_count, count)
print(min_count)


Fixed submission:
n = int(input())
s = input()

count = [float('inf')] * n

# 左端
count[0] = 0
for i in range(1, n):
    if s[i] == 'E':
        count[0] += 1

# 尺取
for i in range(1, n):
    count[i] = count[i-1]
    if s[i-1] == 'W':
        count[i] += 1
    if s[i] == 'E':
        count[i] -= 1

print(min(count))