Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())


def check(n, k):
    while n % k == 0:
        n = n // k
    if n >= k:
        n = n - k * (n // k)
    return n


def count(n):
    total = 0
    cands = set([n, n-1])
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cands.add(i)
            cands.add(n // i)
    for i in range(2, int(n ** 0.5) + 1):
        if (n-1) % i == 0:
            cands.add(i)
            cands.add((n - 1) // i)
    for k in cands:
        if check(n, k) == 1:
            total += 1
    return total


print(count(n))

Fixed submission:
n = int(input())


def check(n, k):
    while n % k == 0:
        n = n // k
    if n >= k:
        n = n - k * (n // k)
    return n


def count(n):
    total = 0
    cands = set([n, n-1])
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cands.add(i)
            cands.add(n // i)
    for i in range(2, int(n ** 0.5) + 1):
        if (n-1) % i == 0:
            cands.add(i)
            cands.add((n - 1) // i)
    for k in cands:
        if k == 1:
            continue
        if check(n, k) == 1:
            total += 1
    return total


print(count(n))
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7


def solve(n, a):
    m = 62
    b = [('0'*m + bin(a[i])[2:])[-1:-m:-1] for i in range(n)]
    cnt_bit = [0] * m
    for i in range(n):
        for j, c in enumerate(b[i]):
            if c == '1':
                cnt_bit[j] += 1
    total = 0
    for i in range(n):
        for j, c in enumerate(b[i]):
            if c == '0':
                total += 2 ** j * cnt_bit[j]
            if c == '1':
                total += 2 ** j * (n - cnt_bit[j])
    return (total//2) % MOD


def bf(n, a):
    total = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            total += (a[i] ^ a[j])
    return total % MOD


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    print(solve(n, a))
    # print(bf(n, a))


Fixed submission:
MOD = 10 ** 9 + 7


def solve(n, a):
    m = 61
    b = [('0'*m + bin(a[i])[2:])[-1:-m:-1] for i in range(n)]
    cnt_bit = [0] * m
    for i in range(n):
        for j, c in enumerate(b[i]):
            if c == '1':
                cnt_bit[j] += 1
    total = 0
    k = 1
    for i in range(m - 1):
        t = 0
        for j in range(n):
            if b[j][i] == '0':
                t += k * cnt_bit[i]
            if b[j][i] == '1':
                t += k * (n - cnt_bit[i])
        t //= 2
        total += t
        k = (k*2 % MOD)
    return total % MOD


def bf(n, a):
    total = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            total += (a[i] ^ a[j])
    return total % MOD


if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))

    print(solve(n, a))
    # print(bf(n, a))
Buggy python submission (verdict: Runtime Error):
n,m = map(int, input().split())
a = set([int(input()) for i in range(m)])

mod = 10**9 + 7
dp = [0] * (n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
if 2 not in a:
    dp[2] = dp[0] + dp[1]
for i in range(3, n+1):
    if i not in a:
        dp[i] = (dp[i-1] + dp[i-2]) % mod
print(dp[n] % mod)
        

Fixed submission:
n, m = map(int, input().split())
a = set([int(input()) for i in range(m)])

mod = 10**9 + 7
dp = [0] * (n + 3)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
if 2 not in a:
    dp[2] = dp[0] + dp[1]
for i in range(3, n + 1):
    if i not in a:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[n] % mod)
Buggy python submission (verdict: Time Limit Exceeded):
h, w = map(int, input().split())
cells = [input() for _ in range(h)]

us = [[0] * w for i in range(h)]
ds = [[0] * w for i in range(h)]
ls = [[0] * w for i in range(h)]
rs = [[0] * w for i in range(h)]

for x in range(w):
    u_cnt = 0
    for y in range(h):
        us[y][x] = u_cnt
        if cells[y][x] == '.':
            u_cnt += 1
        else:
            u_cnt = 0
    d_cnt = 0
    for y in range(h - 1, -1, -1):
        ds[y][x] = d_cnt
        if cells[y][x] == '.':
            d_cnt += 1
        else:
            d_cnt = 0
for y in range(h):
    l_cnt = 0
    for x in range(w):
        ls[y][x] = l_cnt
        if cells[y][x] == '.':
            l_cnt += 1
        else:
            l_cnt = 0

    r_cnt = 0
    for x in range(w - 1, -1, -1):
        rs[y][x] = r_cnt
        if cells[y][x] == '.':
            r_cnt += 1
        else:
            r_cnt = 0

maxv = 0
for y in range(h):
    for x in range(w):
        if cells[y][x] == '#':
            continue
        maxv = max(maxv, us[y][x] + ds[y][x] + ls[y][x] +
                   rs[y][x] + (1 if cells[y][x] == '.' else 0))
print(maxv)


Fixed submission:
h, w = map(int, input().split())
cells = [input() for _ in range(h)]

us = [[0] * w for i in range(h)]
ds = [[0] * w for i in range(h)]
ls = [[0] * w for i in range(h)]
rs = [[0] * w for i in range(h)]

for x in range(w):
    u_cnt = 0
    for y in range(h):
        us[y][x] = u_cnt
        if cells[y][x] == '.':
            u_cnt += 1
        else:
            u_cnt = 0
    d_cnt = 0
    for y in range(h - 1, -1, -1):
        ds[y][x] = d_cnt
        if cells[y][x] == '.':
            d_cnt += 1
        else:
            d_cnt = 0
for y in range(h):
    l_cnt = 0
    for x in range(w):
        ls[y][x] = l_cnt
        if cells[y][x] == '.':
            l_cnt += 1
        else:
            l_cnt = 0

    r_cnt = 0
    for x in range(w - 1, -1, -1):
        rs[y][x] = r_cnt
        if cells[y][x] == '.':
            r_cnt += 1
        else:
            r_cnt = 0

maxv = 0
for y in range(h):
    for x in range(w):
        if cells[y][x] == '#':
            continue
        maxv = max(maxv, us[y][x] + ds[y][x] + ls[y][x] +
                   rs[y][x] + (1 if cells[y][x] == '.' else 0))
print(maxv)
Buggy python submission (verdict: Runtime Error):
n = int(input())

graph = [[] for i in range(n)]
edge_cnt = [0] * n
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    edge_cnt[a-1] += 1
    edge_cnt[b-1] += 1


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

v = 0
for i in range(n):
    if edge_cnt[i] == 1:
        v = i
        break

nodes = [0] * n
total_score = -c[-1]


def dfs(v):
    global total_score
    if nodes[v] > 0:
        return
    nodes[v] = c.pop()
    total_score += nodes[v]
    for nv in graph[v]:
        if nodes[nv] > 0:
            continue
        dfs(nv)


dfs(v)
print(total_score)
print(*nodes, sep=' ')


Fixed submission:
import sys
sys.setrecursionlimit(100000)

n = int(input())

graph = [[] for i in range(n)]
edge_cnt = [0] * n
for i in range(n-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    edge_cnt[a-1] += 1
    edge_cnt[b-1] += 1


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

v = 0
for i in range(n):
    if edge_cnt[i] == 1:
        v = i
        break

nodes = [0] * n
total_score = -c[-1]


def dfs(v):
    global total_score
    if nodes[v] > 0:
        return
    nodes[v] = c.pop()
    total_score += nodes[v]
    for nv in graph[v]:
        if nodes[nv] > 0:
            continue
        dfs(nv)


dfs(v)
print(total_score)
print(*nodes, sep=' ')
Buggy python submission (verdict: Runtime Error):
import heapq

n,k = map(int, input().split())
vs = list(map(int, input().split()))

max_v = -float('inf')
for a in range(max(k,n)):
    total = 0
    minus = []
    for i in range(a):
        total += vs[i]
        if vs[i] < 0:
            heapq.heappush(minus, vs[i])
    for b in range(max(k-a,n-a)):
        c = k - a - b
        if c < 0:
            break
        h = minus[:]
        t = total
        for i in range(b):
            t += vs[n-1-i]
            if vs[n-1-i] < 0:
                heapq.heappush(h, vs[n-1-i])
        for i in range(c):
            if h:
                v = heapq.heappop(h)
                t -= v
        max_v = max(max_v, t)

print(max_v)        


Fixed submission:
import heapq

n, k = map(int, input().split())
vs = list(map(int, input().split()))

max_v = -float('inf')
for a in range(min(k, n)+1):
    total = 0
    minus = []
    for i in range(a):
        total += vs[i]
        if vs[i] < 0:
            heapq.heappush(minus, vs[i])
    max_v = max(max_v, total)
    for b in range(min(k-a, n-a)+1):
        c = k - a - b
        if c < 0:
            break
        h = minus[:]
        t = total
        for i in range(b):
            t += vs[n-1-i]
            if vs[n-1-i] < 0:
                heapq.heappush(h, vs[n-1-i])
        for i in range(c):
            if h:
                v = heapq.heappop(h)
                t -= v
            else:
                break
        max_v = max(max_v, t)

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

q = int(input())

# 中央値との大小で集団を２つに分けて管理したいぞ
_,a,b = map(int, input().split())
a_large = []
a_small = [-a]
cnt_large = 0
cnt_small = 1
mean = 0
cons = b
total = 0

for i in range(q-1):
    query = input()
    if query[0] == '1':
        _,a,b = map(int, query.split())
        cons = cons + b
        if a < -a_small[0]:
            # 最大ヒープ
            heapq.heappush(a_small, -a)
            total += abs(a - -a_small[0])
            cnt_small += 1
            if cnt_small > cnt_large + 1:
                old_mean = -a_small[0]
                heapq.heappush(a_large, -heapq.heappop(a_small))
                cnt_small -= 1
                cnt_large += 1
                new_mean = -a_small[0]
                total += (new_mean- old_mean) * (cnt_large - cnt_small)
        else:
            # 最小ヒープ
            heapq.heappush(a_large, a)
            total += abs(a - -a_small[0])
            cnt_large += 1
            if cnt_large > cnt_small:
                old_mean = -a_small[0]
                heapq.heappush(a_small, -heapq.heappop(a_large))
                cnt_small += 1
                cnt_large -= 1
                new_mean = -a_small[0]
                total += (new_mean-old_mean) * (cnt_large - cnt_small)
    else:
        # total = 0
        x = -a_small[0]
        # for small in a_small:
        #     total += abs(x+small)
        # for large in a_large:
        #     total += abs(x-large)
        print(x, total+cons)


        

Fixed submission:
import heapq

q = int(input())

# 中央値との大小で集団を２つに分けて管理したいぞ
_,a,b = map(int, input().split())
a_large = []
a_small = [-a]
cnt_large = 0
cnt_small = 1
mean = 0
cons = b
total = 0

for i in range(q-1):
    query = input()
    if query[0] == '1':
        _,a,b = map(int, query.split())
        cons = cons + b
        if a < -a_small[0]:
            # 最大ヒープ
            heapq.heappush(a_small, -a)
            total += -(a - -a_small[0])
            cnt_small += 1
            if cnt_small > cnt_large + 1:
                old_mean = -a_small[0]
                heapq.heappush(a_large, -heapq.heappop(a_small))
                cnt_small -= 1
                cnt_large += 1
                new_mean = -a_small[0]
                total += (new_mean- old_mean) * (cnt_large - cnt_small)
        else:
            # 最小ヒープ
            heapq.heappush(a_large, a)
            total += (a - -a_small[0])
            cnt_large += 1
            if cnt_large > cnt_small:
                old_mean = -a_small[0]
                heapq.heappush(a_small, -heapq.heappop(a_large))
                cnt_small += 1
                cnt_large -= 1
                new_mean = -a_small[0]
                total += (new_mean-old_mean) * (cnt_large - cnt_small)
    else:
        x = -a_small[0]
        print(x, total+cons)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
s = input()
upper = {
    'A': 'a',
    'B': 'b',
    'C': 'c',
}
print(s[:k] + upper[s[k]] + s[k+1:])

Fixed submission:
n, k = map(int, input().split())
s = input()
upper = {
    'A': 'a',
    'B': 'b',
    'C': 'c',
}
print(s[:k-1] + upper[s[k-1]] + s[k:])
Buggy python submission (verdict: Runtime Error):
import unittest


def solve_small(n):
    total = 0
    for m in range(1, n):
        if n // m == n % m:
            total += m
    return total


def solve(n):
    conds = set()
    conds.add(n-1)
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            conds.add(i-1)
            conds.add(n // i - 1)
    total = 0
    for m in list(conds):
        if n // m == n % m:
            total += m
    return total


def main():
    n = int(input())
    result = solve(n)
    print(result)


if __name__ == "__main__":
    main()


class Test(unittest.TestCase):
    def test_solve_1(self):
        n = 8
        actual = solve(n)
        expected = 10
        self.assertEqual(actual, expected)

    def test_solve_2(self):
        n = 1000000000000
        actual = solve(n)
        expected = 2499686339916
        self.assertEqual(actual, expected)


Fixed submission:
import unittest


def solve(n):
    used = set()
    total = 0
    for i in range(1, int(n ** 0.5)+1):
        if n % i > 0:
            continue
        d = n // i
        cand = [i-1, d-1]
        for c in cand:
            if c not in used and c > 0 and n % c == n // c:
                total += c
                used.add(c)

    return total


def main():
    n = int(input())
    result = solve(n)
    print(result)


if __name__ == "__main__":
    main()


class Test(unittest.TestCase):
    def test_solve_1(self):
        n = 8
        actual = solve(n)
        expected = 10
        self.assertEqual(actual, expected)

    def test_solve_2(self):
        n = 1000000000000
        actual = solve(n)
        expected = 2499686339916
        self.assertEqual(actual, expected)
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
print(max(a,b) + max(max(a,b)-1, min(a,b))


Fixed submission:
a, b = map(int, input().split())
print(max(a,b) + max(max(a,b)-1, min(a,b)))

Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
print(max(a,b) + max(max(a,b), min(a,b))

Fixed submission:
a, b = map(int, input().split())
print(max(a,b) + max(max(a,b)-1, min(a,b)))
Buggy python submission (verdict: Runtime Error):
v=[int(input()) for_ in range(6)]
print('Yay!' if v[4]-v[0]<=v[5] else ':(')


Fixed submission:
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

if e-a <= k:
    print('Yay!')
else:
    print(':(')

Buggy python submission (verdict: Runtime Error):
v=[int(input()) for_ in range(6)]
print('Yay!' if all([v[i+1]-v[i]<=v[5] for i in range(4)]) else ':(')


Fixed submission:
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

if e-a <= k:
    print('Yay!')
else:
    print(':(')

Buggy python submission (verdict: Runtime Error):
v=[int(input()) for_ in range(6)]
print('Yay!' if all([abs(v[i]-v[i+1])<=v[5] for i in range(4)) else ':(')

Fixed submission:
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())

if e-a <= k:
    print('Yay!')
else:
    print(':(')
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
l = n+1
while l > len(s):
    l = len(s)
    s = s.replace('01','')
    s = s.replace('10','')
print(n-len(s))

Fixed submission:
s = input()
x = 0
y = 0
cnt = 0
for c in s:
    if c == '0':
        if y > 0:
            y -= 1
            cnt += 2
        else:
            x += 1
    else:
        if x >0:
            x -= 1
            cnt += 2
        else:
            y += 1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
import collections

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

graph = [[] for i in range(n)]
in_count = [0] * n
out_count = [0] * n
for i in range(n + m - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    in_count[b] += 1
root = in_count.index(0)

parent = [0] * n
dq = collections.deque()
dq.append((-1, root))
while dq:
    p, v = dq.popleft()
    parent[v] = p
    for nv in graph[v]:
        dq.append((v, nv))

for p in parent:
    print(p+1)


Fixed submission:
import collections

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

in_graph = [[] for i in range(n)]
out_graph = [[] for i in range(n)]
in_count = [0] * n
out_count = [0] * n
for i in range(n + m - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    out_graph[a].append(b)
    out_count[a] += 1
    in_graph[b].append(a)
    in_count[b] += 1
root = in_count.index(0)
ranks = [0] * n
parent = [0] * n
dq = collections.deque()
for i in range(n):
    if out_count[i] == 0:
        dq.append(i)
rank = n
while dq:
    v = dq.popleft()
    ranks[v] = rank
    rank -= 1
    for nv in in_graph[v]:
        out_count[nv] -= 1
        if out_count[nv] == 0:
            dq.append(nv)

for i in range(n):
    max_v = -1
    max_rank = -1
    for v in in_graph[i]:
        if max_rank < ranks[v]:
            max_rank = ranks[v]
            max_v = v
    print(max_v+1)

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

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

graph = [[] for i in range(n)]
in_count = [0] * n
out_count = [0] * n
for i in range(n + m - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    in_count[b] += 1
root = in_count.index(0)

parent = [0] * n
dq = collections.deque()
dq.append((-1, root))
while dq:
    p, v = dq.popleft()
    parent[v] = p
    for nv in graph[v]:
        dq.append((v, nv))

for p in parent:
    print(p+1)


Fixed submission:
import collections

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

in_graph = [[] for i in range(n)]
out_graph = [[] for i in range(n)]
in_count = [0] * n
out_count = [0] * n
for i in range(n + m - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    out_graph[a].append(b)
    out_count[a] += 1
    in_graph[b].append(a)
    in_count[b] += 1
root = in_count.index(0)
ranks = [0] * n
parent = [0] * n
dq = collections.deque()
for i in range(n):
    if out_count[i] == 0:
        dq.append(i)
rank = n
while dq:
    v = dq.popleft()
    ranks[v] = rank
    rank -= 1
    for nv in in_graph[v]:
        out_count[nv] -= 1
        if out_count[nv] == 0:
            dq.append(nv)

for i in range(n):
    max_v = -1
    max_rank = -1
    for v in in_graph[i]:
        if max_rank < ranks[v]:
            max_rank = ranks[v]
            max_v = v
    print(max_v+1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
input = sys.stdin.readline

max_cost = 10**9
n, k = map(int, input().split())
hs = list(map(int, input().split()))
min_cost = [float('inf')] * n
graph = [[(j, abs(hs[i] - hs[j])) for j in range(i+1, i+k+1) if j < n] for i in range(n)]

def dijkstra(source, target):
    hq = [(0, source)]
    while hq:
        cost, vertex = heapq.heappop(hq)
        min_cost[vertex] = cost
        if vertex == target:
            return min_cost[vertex]
        for adjacency_vertex, adjacency_cost in graph[vertex]:
            heapq.heappush(hq, (cost + adjacency_cost, adjacency_vertex))

print(dijkstra(0, n-1))


Fixed submission:
n, k = map(int, input().split())
hs = list(map(int, input().split()))
min_cost = [float('inf')] * n
min_cost[0] = 0
for i in range(1, n):
    min_cost[i] = min([min_cost[i-j] + abs(hs[i] - hs[i-j]) for j in range(1, k+1) if i-j >= 0])
print(min_cost[n-1])

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


Fixed submission:
n, k = map(int, input().split())
hs = list(map(int, input().split()))
min_cost = [float('inf')] * n
min_cost[0] = 0
for i in range(1, n):
    min_cost[i] = min([min_cost[i-j] + abs(hs[i] - hs[i-j]) for j in range(1, k+1) if i-j >= 0])
print(min_cost[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
hs = list(map(int, input().split()))
min_cost = [float('inf')] * n
min_cost[0] = 0
for i in range(n):
    for j in range(1, k+1):
        if i+j < n:
            min_cost[i+j] = min(min_cost[i+j], min_cost[i] + abs(hs[i] - hs[i+j]))
        else:
            continue
print(min_cost[n-1])


Fixed submission:
n, k = map(int, input().split())
hs = list(map(int, input().split()))
min_cost = [float('inf')] * n
min_cost[0] = 0
for i in range(1, n):
    min_cost[i] = min([min_cost[i-j] + abs(hs[i] - hs[i-j]) for j in range(1, k+1) if i-j >= 0])
print(min_cost[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,w = map(int, input().split())
max_value = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    weight, value = map(int, input().split())
    for j in range(1, weight):
        max_value[i][j] = max_value[i-1][j]
    for j in range(weight, w+1):
        max_value[i][j] = max(max_value[i-1][j], max_value[i-1][j-weight] + value)

print(max_value[n][w])

Fixed submission:
n,w = map(int, input().split())
max_value = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    weight, value = map(int, input().split())
    for j in range(1, weight):
        max_value[i][j] = max_value[i-1][j]
    for j in range(weight, w+1):
        max_value[i][j] = max(max_value[i-1][j], max_value[i-1][j-weight] + value)

print(max_value[n][w])

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

item = []
for i in range(n):
    weight, value = map(int, input().split())
    item.append((weight, value))

max_value = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    weight, value = item[i-1]
    for j in range(1, weight):
        max_value[i][j] = max(max_value[i-1][j], max_value[i][j-1])
    for j in range(weight, w+1):
        max_value[i][j] = max(max_value[i-1][j], max_value[i][j-1], max_value[i-1][j-weight] + value)

print(max_value[n][w])

Fixed submission:
n,w = map(int, input().split())
max_value = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    weight, value = map(int, input().split())
    for j in range(1, weight):
        max_value[i][j] = max_value[i-1][j]
    for j in range(weight, w+1):
        max_value[i][j] = max(max_value[i-1][j], max_value[i-1][j-weight] + value)

print(max_value[n][w])

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

item = []
for i in range(n):
    weight, value = map(int, input().split())
    item.append((weight, value))
item.sort()

max_value = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    weight, value = item[i-1]
    for j in range(1, w+1):
        max_value[i][j] = max(max_value[i-1][j], max_value[i][j-1], max_value[i-1][j-weight] + value if j-weight >= 0 else 0)


print(max_value[n][w])

Fixed submission:
n,w = map(int, input().split())
max_value = [[0]*(w+1) for _ in range(n+1)]
for i in range(1, n+1):
    weight, value = map(int, input().split())
    for j in range(1, weight):
        max_value[i][j] = max_value[i-1][j]
    for j in range(weight, w+1):
        max_value[i][j] = max(max_value[i-1][j], max_value[i-1][j-weight] + value)

print(max_value[n][w])
Buggy python submission (verdict: Runtime Error):
import math
n, p = map(int, input().split())
if n == 1:
    print(p)
    exit()

res = 1
v = 2
while v <= p**(1/n)+1:
    if p % v == 0:
        vn = math.pow(v, n)
        while p % vn == 0:
            res *= v
            p /= vn
    v += 1

print(res)

Fixed submission:
import collections

N, p = map(int, input().split())
if N == 1:
    print(p)
    exit()

def prime_decomposition(n):
    # 素因数分解
    if n < 2:
        return []
    prime_factors = []
    while n % 2 == 0:
        prime_factors.append(2)
        n >>= 1

    while n % 3 == 0:
        prime_factors.append(3)
        n //= 3

    a = 5
    b = 7
    while a ** 2 <= n:
        if n % a == 0:
            prime_factors.append(a)
            n //= a
        elif n % b == 0:
            prime_factors.append(b)
            n //= b
        else:
            a += 6
            b += 6
    if n > 1:
        prime_factors.append(n)
    return prime_factors

res = 1
pf = collections.Counter(prime_decomposition(p))
for v, c in pf.items():
    while c >= N:
        res *= v
        c -= N
print(res)