Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
le = [[p[0]-p[1], p[0]+p[1]] for p in xl]
le.sort(key = lambda x　: x[1])

ans = 0
right = -(10 ** 9) -　1
for i in range(n):
    if right <= le[i][0]:
        ans += 1
        right = le[i][1]

print(ans)

Fixed submission:
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
le = [[p[0]-p[1], p[0]+p[1]] for p in xl]
le.sort(key = lambda x : x[1])

ans = 0
right = -(10 ** 9) - 1
for i in range(n):
    if right <= le[i][0]:
        ans += 1
        right = le[i][1]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from operator import itemgetter
from itertools import permutations

N = int(input())
XL = [tuple(map(int, input().split())) for _ in range(N)]

XL = sorted(XL, key=itemgetter(0))

for i in range(N):
    for remove in permutations(XL, i):
        remained = [i for i in XL if i not in remove]
        edge = []
        for remain in remained:
            x, l = remain
            edge.append(x-l)
            edge.append(x+l)
        if edge == sorted(edge):
            print(len(remained))
            exit()

Fixed submission:
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]
le = [[p[0]-p[1], p[0]+p[1]] for p in xl]
le.sort(key = lambda x : x[1])

ans = 0
right = -(10 ** 9) - 1
for i in range(n):
    if right <= le[i][0]:
        ans += 1
        right = le[i][1]

print(ans)
Buggy python submission (verdict: Runtime Error):
A, B, K = map(int, input().split())

elif A > K:
    print(A-K, B)
else:
    print(0, max(0, B-(K-A)))


Fixed submission:
A, B, K = map(int, input().split())

if A > K:
    print(A-K, B)
else:
    print(0, max(0, B-(K-A)))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))

MOD = 10**9 + 7

ans = 0
two_factor = 1
for d in range(60):
    n0 = 0
    n1 = 0
    for i in range(N):
        if A[i] & (1<<d):
            n1 += 1
        else:
            n0 += 1
    tmp = (1<<d) % MOD
    n = n0 * n1 % MOD
    tmp = tmp * n % MOD
    ans = (ans + tmp) % MOD

print(ans)


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

mod = 10**9 + 7

ans = 0
for i in range(60):
    X = sum([1 for x in A if (x >> i) & 1])
    ans += (1 << i) * X * (N - X)
    ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

N = int(input())
S = input()

ans = set()
for comb in combinations(range(len(S)), 3):
    password = ""
    for c in comb:
        password += S[c]
    ans.add(password)

print(len(ans))

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

ans = 0
for i in range(10):
    a = S.find(str(i))
    if a == -1: continue
    for j in range(10):
        b = S.find(str(j), a + 1)
        if b == -1: continue
        for k in range(10):
            if S.find(str(k), b + 1) != -1:
                ans += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
M = int(input())
N = []

ans = 0
prev_d = 0
for i in range(M):
    d, c = map(int, input().split())
    N += [d] * c
    ans += c
    if prev_d + d > 9:
        ans += 1
    prev_d = d

print(ans-1)


Fixed submission:
M = int(input())

s = 0
dig = 0
for i in range(M):
    d, c = map(int, input().split())
    s += d * c
    dig += c

print(dig - 1 + (s - 1) // 9)
Buggy python submission (verdict: Time Limit Exceeded):
def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**6 + 1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

X, Y = map(int, input().split())

if X % 3 !=0 or X % 3 != 0:
    print(0)
    exit()

A = (2*Y - X) // 3
B = (2*X - Y) // 3

print(cmb(A+B, A, mod))


Fixed submission:
X, Y = map(int, input().split())

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9 + 7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range( 2, N +1):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

if ((X + Y) % 3 != 0):
    print(0)
    exit()

A = (2 * Y - X) // 3
B = (2 * X - Y) // 3

print(cmb(A + B, A))
Buggy python submission (verdict: Runtime Error):
import math

def prime_factorize(n):
    res = []
    for i in range(2, int(n**(1/2))+1):
        if n % i != 0: continue
        num = 0
        while n % i == 0:
            num += 1
            n /= i
        res.append((i, num))
    if n != 1:
        res.append((n, 1))
    
    return res

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

gcdAB = math.gcd(A, B)
pf = prime_factorize(gcdAB)

print(len(pf)+1)


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

def prime_factorize(n):
    res = []
    for i in range(2, int(n**(1/2))+1):
        if n % i != 0: continue
        num = 0
        while n % i == 0:
            num += 1
            n /= i
        res.append((i, num))
    if n != 1:
        res.append((n, 1))
    
    return res

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

gcdAB = gcd(A, B)
pf = prime_factorize(gcdAB)

print(len(pf)+1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)

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

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

c = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    c[p-1] += x

def dfs(now, prev=-1):
    for next in g[now]:
        if next == prev:
            continue

        c[next] += c[now]
        dfs(next, now)

dfs(0)
print(*c)

Fixed submission:
from collections import deque

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

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

c = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    c[p-1] += x

q = deque([0])
flag = [False] * n
while q:
    v = q.pop()
    flag[v] = True
    for e in g[v]:
        if flag[e]:
            continue
        c[e] += c[v]
        q.append(e)

print(*c)

Buggy python submission (verdict: Runtime Error):
n, q = map(int, input().split())

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

c = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    c[p-1] += x

def dfs(now, prev=-1):
    for next in g[now]:
        if next != prev:
            c[next] += c[now]
            dfs(next, now)

dfs(0)
print(*c)

Fixed submission:
from collections import deque

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

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

c = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    c[p-1] += x

q = deque([0])
flag = [False] * n
while q:
    v = q.pop()
    flag[v] = True
    for e in g[v]:
        if flag[e]:
            continue
        c[e] += c[v]
        q.append(e)

print(*c)

Buggy python submission (verdict: Runtime Error):
n, q = map(int, input().split())

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

c = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    c[p-1] += x

def dfs(now, prev=-1):
    for next in g[now]:
        if next != prev:
            c[next] += c[now]
            dfs(next, now)

dfs(0)
print(*c)

Fixed submission:
from collections import deque

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

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

c = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    c[p-1] += x

q = deque([0])
flag = [False] * n
while q:
    v = q.pop()
    flag[v] = True
    for e in g[v]:
        if flag[e]:
            continue
        c[e] += c[v]
        q.append(e)

print(*c)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

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

cnt = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    cnt[a].append(b)

t = []
ans = 0
for i in range(1, m+1):
    t += cnt[i]
    t.sort()
    if t: ans += t.pop()

print(ans)


Fixed submission:
import heapq
from collections import defaultdict

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

cnt = defaultdict(list)
for _ in range(n):
    a, b = map(int, input().split())
    cnt[a].append(b)

t = []
heapq.heapify(t)
ans = 0
for i in range(1, m+1):
    for j in cnt[i]:
        heapq.heappush(t, -j)
    if t: ans -= heapq.heappop(t)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = list(input())
n = len(s)

mod = 10**9 + 7

dp = [[0] * 13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(13):
        if s[i] == '?':
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j] 
                dp[i+1][(j*10+k)%13] %= mod
        else:
            k = int(s[i])
            dp[i+1][(j*10+k)%13] += dp[i][j]
            dp[i+1][(j*10+k)%13] %= mod

print(dp[n][5])


Fixed submission:
s = list(input())
n = len(s)

mod = 10**9 + 7

dp = [[0] * 13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    for j in range(13):
        if s[i] == '?':
            for k in range(10):
                dp[i+1][(j*10+k)%13] += dp[i][j] 
                dp[i+1][(j*10+k)%13] %= mod
        else:
            k = int(s[i])
            dp[i+1][(j*10+k)%13] += dp[i][j]
            dp[i+1][(j*10+k)%13] %= mod

print(dp[n][5])
Buggy python submission (verdict: Runtime Error):
import math

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

num1 = B // C - (A-1) // C
num2 = B // D - (A-1) // D
gcdCD = C * D // math.gcd(C, D)
num3 = B // gcdCD - (A-1) // gcdCD

print(B - A - num1 - num2 + num3 + 1)

Fixed submission:
from fractions import gcd

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

num1 = B // C - (A-1) // C
num2 = B // D - (A-1) // D
gcdCD = C * D // gcd(C, D)
num3 = B // gcdCD - (A-1) // gcdCD

print(B - A - num1 - num2 + num3 + 1)
Buggy python submission (verdict: Runtime Error):
from collections import deque

n = int(input())

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

c = list(map(int, input().split()))
c.sort()

ans = []
s = [0] * n
que = deque([0])
while que:
    t = que.popleft()
    ans.append(c.pop())
    s[t] = 1
    for e in g[t]:
        if not s[e]:
            que.append(e)

print(sum(c) - max(c))
print(*ans)


Fixed submission:
import heapq

n = int(input())

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

c = list(map(lambda x: -int(x), input().split()))
heapq.heapify(c)
print(min(c) - sum(c))

ans = []
s = [-1] * n
leaf = -1
for i, a in enumerate(g):
    if len(a) == 1:
        leaf = i
        break

que = [leaf]
while que:
    t = que.pop()
    for e in g[t]:
        if s[e] == -1:
            s[e] = -heapq.heappop(c)
            que.append(e)

print(*s)
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)]

heapq.heapify(A)
for b, c in BC:
    for i in range(b):
        a = heapq.heappop(A)
        if a < c:
            heapq.heappush(A, c)
        else:
            heapq.heappush(A, a)

print(sum(A))

Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
BC = sorted(BC, key = lambda x : x[1], reverse=True)

n = 0
for b, c in BC:
    n += b
    A += [c] * b

    if n >= N:
        break

A = sorted(A, reverse=True)
print(sum(A[:N]))
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(500*500)

N = int(input())
edges = [list(map(int, input().split())) for _ in range(N-1)]

A = [[] for _ in range(N+1)]

for edge in edges:
    A[edge[0]].append(edge[1], edge[2])
    A[edge[1]].append(edge[0], edge[2])

depth = [-1] * (N-1)
depth[1] = 0

def dfs(A, s):
    for v in A[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs[A, v[0]]

dfs[A, 1]
for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)

Fixed submission:
import sys
sys.setrecursionlimit(500*500)

N = int(input())
edges = [list(map(int, input().split())) for _ in range(N-1)]

A = [[] for _ in range(N+1)]

for edge in edges:
    A[edge[0]].append([edge[1], edge[2]])
    A[edge[1]].append([edge[0], edge[2]])

depth = [-1] * (N+1)
depth[1] = 0

def dfs(A, s):
    for v in A[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs(A, v[0])

dfs(A, 1)
for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)
Buggy python submission (verdict: Runtime Error):
n = int(input())

ans = 0
for k in range(1, int(n**(1/2))+1):
    m = (n - k) // k
    if n // m == n % m:
        ans += m

print(ans)


Fixed submission:
n = int(input())

ans = 0
for k in range(1, int(n**(1/2))+1):
    m = (n - k) // k
    if m <= 0: continue
    if n // m == n % m:
        ans += m

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

d = [[-1] * w for _ in range(h)]
que = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append((j, i))
            d[i][j] = 0

dxdy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

ans = 0
while que:
    x, y = que.popleft()
    for dx, dy in dxdy:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and s[ny][nx] == -1:
            que.append((nx, ny))
            s[ny][nx] = s[y][x] + 1
            ans = max(ans, s[ny][nx])

print(ans)


Fixed submission:
from collections import deque

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

d = [[-1] * w for _ in range(h)]
que = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append((j, i))
            d[i][j] = 0

dxdy = [(1, 0), (-1, 0), (0, 1), (0, -1)]

ans = 0
while que:
    x, y = que.popleft()
    for dx, dy in dxdy:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == -1:
            que.append((nx, ny))
            d[ny][nx] = d[y][x] + 1
            ans = max(ans, d[ny][nx])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    
    divisors.sort()
    return divisors

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

div1 = set(make_divisors(a[0]))
div2 = set(make_divisors(a[1]))
common = div1 | div2

cnt = defaultdict(int)
for i in range(n):
    for j in common:
        if a[i] % j == 0:
            cnt[j] += 1

for k, v in sorted(cnt.items(), reverse=True):
    if v == n or v == n-1:
        print(k)
        exit()


Fixed submission:
from collections import defaultdict

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    
    divisors.sort()
    return divisors

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

div1 = set(make_divisors(a[0]))
div2 = set(make_divisors(a[1]))
common = div1 | div2

cnt = defaultdict(int)
for i in range(n):
    for j in common:
        if a[i] % j == 0:
            cnt[j] += 1

for k, v in sorted(cnt.items(), reverse=True):
    if v == n or v == n-1:
        print(k)
        exit()
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
s = list(input())

cnt = []
if s[0] == '0': cnt.append(0)

i = 0
while i < n:
    j = i
    while j < n and s[j] == s[i]:
        j += 1
    cnt.append(j- i)
    i = j
if s[-1] == '0': cnt.append(0)

cs = [0] * (len(cnt)+1)
for i in range(len(cnt)):
    cs[i+1] = cs[i] + cnt[i]

ans = 0
m = 2 * k + 1
for i in range(0, len(cnt), 2):
    ans = max(ans, cs[i+m] - cs[i])

print(ans)


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

cnt = []
if s[0] == '0': cnt.append(0)
i = 0
while i < n:
    j = i
    while j < n and s[j] == s[i]:
        j += 1
    cnt.append(j- i)
    i = j
if s[-1] == '0': cnt.append(0)

m = len(cnt)
cs = [0] * (m+1)
for i in range(m):
    cs[i+1] = cs[i] + cnt[i]

ans = 0
for l in range(0, m+1, 2):
    r = l + 2 * k + 1
    if r > m: r = m
    ans = max(ans, cs[r] - cs[l])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())

ab = []
ba = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a, b))
    ba.append((b, a))

ab.sort(key=lambda x:x[0])
ba.sort(key=lambda x:x[0])

ans = 0
for i in range(n):
    if i % 2 == 0:
        if ab[0][0] == ab[-1][0]:
            b, a = ba.pop()
            ab.remove((a, b))
        else:
            a, b = ab.pop()
            ba.remove((b, a))
        ans += a
    else:
        if ba[0][0] == ba[-1][0]:
            a, b = ab.pop()
            ba.remove((b, a))
        else:
            b, a = ba.pop()
            ab.remove((a, b))
        ans -= b
print(ans)


Fixed submission:
n = int(input())

ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a+b, a, b))

ab.sort(key= lambda x:x[0])

ans = 0
for i in range(n):
    v, a, b = ab.pop()
    if i % 2 == 0:
        ans += a
    else:
        ans -= b

print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())

ia = []
ib = []
for i in range(n):
    a, b = map(int, input().split())
    ia.append((i, a))
    ib.append((i, b))

ia.sort(key=lambda x:x[1])
ib.sort(key=lambda x:x[1])

ans = 0
for i in range(n):
    if i % 2 == 0:
        if ia[0][1] == ia[-1][1]:
            j, b = ib.pop()
            _, a = ia.pop(j)
        else:
            j, a = ia.pop()
            _, b = ib.pop(j)
        ans += a
    else:
        if ib[0][1] == ib[-1][1]:
            j, a = ia.pop()
            _, b = ib.pop(j)
        else:
            j, b = ib.pop()
            _, a = ia.pop(j)
        ans -= b
print(ans)


Fixed submission:
n = int(input())

ab = []
for i in range(n):
    a, b = map(int, input().split())
    ab.append((a+b, a, b))

ab.sort(key= lambda x:x[0])

ans = 0
for i in range(n):
    v, a, b = ab.pop()
    if i % 2 == 0:
        ans += a
    else:
        ans -= b

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
h = tuple(map(int,input().split()))

dp = [0] + [float("inf")]*(n-1)
for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[-1])

Fixed submission:
import numpy as np

N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)
for i in range(1, N):
    dp[i] = min(dp[max(0,i-K):i]+abs(h[max(0,i-K):i]-h[i]))

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):
    dp[i] = min([dp[max(0,i-j)]+abs(h[max(0,i-j)] - h[i]) for j in range(1,K+1)])

print(dp[-1])

Fixed submission:
import numpy as np

N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)
for i in range(1, N):
    dp[i] = min(dp[max(0,i-K):i]+abs(h[max(0,i-K):i]-h[i]))

print(dp[-1])

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

dp = [float("inf")] * N
dp[0] = 0

for i in range(1, N):
    for j in range(1, K+1):
        if i - j < 0:
            break
        else:
            step = abs(h[i] - h[i-j])
            dp[i] = min(dp[i], dp[i-j]+step)

print(dp[N-1])

Fixed submission:
import numpy as np

N, K = map(int, input().split())
h = np.array(list(map(int, input().split())))

dp = np.zeros(N, dtype=int)
for i in range(1, N):
    dp[i] = min(dp[max(0,i-K):i]+abs(h[max(0,i-K):i]-h[i]))

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (W+1) for _ in range(N)]

for i in range(N):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]])

print(max(dp[N-1]))

Fixed submission:
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (W+1) for _ in range(N)]

for i in range(N):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]])

print(max(dp[N-1]))
Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (W+1) for _ in range(N)]

for i in range(N):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], v[i]+dp[i-1][j-w[i]])

print(max(dp[N-1]))

Fixed submission:
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [0] + [float("inf")] * 10**5

for i in range(N):
    for j in range(10**5, v[i]-1, -1):
        dp[j] = min(dp[j], dp[j-v[i]] + w[i])

res = 0
for v, e in enumerate(dp):
    if e <= W:
        res = v

print(res)
Buggy python submission (verdict: Runtime Error):
n = int(input())
p = [int(input()) for _ in range(n)]

q = [0] * (n+1)
for i in range(n):
    q[p[i]] = q[p[i]-1] + 1

print(q - max(q))


Fixed submission:
n = int(input())
p = [int(input()) for _ in range(n)]

q = [0] * (n+1)
for i in range(n):
    q[p[i]] = q[p[i]-1] + 1

print(n - max(q))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

s = list(input())
n = len(s)
k = int(input())

part = set()
for i in range(n):
    for j in range(i, n):
        part.add("".join(s[i:j+1]))

print(sorted(part)[k-1])


Fixed submission:
s = list(input())
n = len(s)
k = int(input())

part = set()
for i in range(n):
    for j in range(k):
        part.add("".join(s[i:i+j+1]))

print(sorted(part)[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

s = list(input())
n = len(s)
k = int(input())

part = defaultdict(set)
for i in range(n):
    for j in range(i, n):
        part[s[i]].add("".join(s[i:j+1]))

cnt = 0
for i in range(ord('a'), ord('z')+1):
    m = len(part[chr(i)])
    if cnt < k <= cnt + m:
        l = sorted(list(part[chr(i)]))
        print(l[k-cnt-1])
        exit()
    cnt += m


Fixed submission:
s = list(input())
n = len(s)
k = int(input())

part = set()
for i in range(n):
    for j in range(k):
        part.add("".join(s[i:i+j+1]))

print(sorted(part)[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

s = list(input())
n = len(s)
k = int(input())

part = defaultdict(set)
for i in range(n):
    for j in range(i, n):
        part[s[i]].add("".join(s[i:j+1]))

cnt = 0
for i in range(ord('a'), ord('z')+1):
    m = len(part[chr(i)])
    if cnt < k <= cnt + m:
        l = sorted(list(part[chr(i)]))
        print(l[k-cnt-1])
        exit()
    cnt += m


Fixed submission:
s = list(input())
n = len(s)
k = int(input())

part = set()
for i in range(n):
    for j in range(k):
        part.add("".join(s[i:i+j+1]))

print(sorted(part)[k-1])