Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
r = [list(map(int, input().split())) for _ in range(N)]
r.sort()

l = [r[0]]
r = r[1:]
while len(r) > 0:
    x1, l1 = l[-1]
    x2, l2 = r[0]
    if (x1+l1) > (x2-l2):
        if (x1+l1) > (x2+l2):
            l.pop()
            l.append(r[0])
            r.pop(0)
        else:
            r.pop(0)
    else:
        l.append(r[0])
        r.pop(0)
print(len(l))


Fixed submission:
N = int(input())
r = [list(map(int, input().split())) for _ in range(N)]
r.sort()

l = r[0]
ri = 1
ans = N
while ri < N:
    x1, l1 = l
    x2, l2 = r[ri]
    if (x1+l1) > (x2-l2):
        if (x1+l1) > (x2+l2):
            l = r[ri]
            ri += 1
        else:
            ri += 1
        ans -= 1
    else:
        l = r[ri]
        ri += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


N, K = map(int, input().split())
R = N-K

for i in range(K):
    a = cmb(K-1, i)
    b = cmb(R+1, i+1)
    print((a*b) % (10**9+7))


Fixed submission:
from operator import mul
from functools import reduce


def cmb(n, r):
    if r > n:
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


N, K = map(int, input().split())
R = N-K

for i in range(K):
    a = cmb(K-1, i)
    b = cmb(R+1, i+1)
    print((a*b) % (10**9+7))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xy.sort()
h = defaultdict(int)
for x, y in xy:
    h[(x, y)] = True
mx, my = xy[-1]
ans = 10**10
for i in range(n-1):
    x1, y1 = xy[i]
    for j in range(i+1, n):
        x2, y2 = xy[i+1]
        z1 = x2-x1
        z2 = y2-y1

        t = set()
        k = 0
        a = 0
        while k < n and len(t) < n:
            xk, yk = xy[k]
            if (xk, yk) not in t:
                a += 1
                while xk <= mx and yk <= my:
                    if (xk, yk) in h:
                        t.add((xk, yk))
                    xk += z1
                    yk += z2
            k += 1
        if a < ans:
            ans = a

print(ans)


Fixed submission:
n, k = map(int, input().split())
l = [1]*k
n -= sum(l)
l[0] += n
print(max(l)-min(l))

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xy.sort()
h = defaultdict(int)
for x, y in xy:
    h[(x, y)] = True
mx, my = xy[-1]
ans = 10**10
for i in range(n-1):
    x1, y1 = xy[i]
    for j in range(i+1, n):
        x2, y2 = xy[i+1]
        z1 = x2-x1
        z2 = y2-y1

        t = set()
        k = 0
        a = 0
        while k < n and len(t) < n:
            xk, yk = xy[k]
            if (xk, yk) not in t:
                a += 1
                while xk <= mx and yk <= my:
                    if (xk, yk) in h and (xk, yk) not in t:
                        t.add((xk, yk))
                    xk += z1
                    yk += z2
            k += 1
        if a < ans:
            ans = a

print(ans)


Fixed submission:
n, k = map(int, input().split())
l = [1]*k
n -= sum(l)
l[0] += n
print(max(l)-min(l))

Buggy python submission (verdict: Runtime Error):
N=int(input())
point=[]
merge=0
for num in range(0,N):
    x,y=map(int,input().split())
    point.append([x,y])
p=0
q=0
point.sort()
ans=0
for i in range(0,N-1):
    for j in range(i+1,N):
        p=point[j][0]-point[i][0]
        q=point[j][1]-point[i][1]
        merge=0
        for k in range(0,N):
            if([point[k][0]+p,point[k][1]+q] in point):
                merge+=1
        ans=max(ans,merge)
print(N-ans)


Fixed submission:
n, k = map(int, input().split())
l = [1]*k
n -= sum(l)
l[0] += n
print(max(l)-min(l))

Buggy python submission (verdict: Runtime Error):
N=int(input())
point=[]
merge=0
for num in range(0,N):
    x,y=map(int,input().split())
    point.append([x,y])
p=0
q=0
point.sort()
ans=0
for i in range(0,N-1):
    for j in range(i+1,N):
        p=point[j][0]-point[i][0]
        q=point[j][1]-point[i][1]
        merge=0
        for k in range(0,N):
            if([point[k][0]+p,point[k][1]+q] in point):
                merge+=1
        ans=max(ans,merge)
print(N-ans)


Fixed submission:
n, k = map(int, input().split())
l = [1]*k
n -= sum(l)
l[0] += n
print(max(l)-min(l))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
xy.sort()
d = defaultdict(int)
for i in range(n-1):
    x1, y1 = xy[i]
    x2, y2 = xy[i+1]
    d["%d:%d" % (x2-x1, y2-y1)] += 1

print(n-max(d.values()))


Fixed submission:
N=int(input())
point=[]
merge=0
for num in range(0,N):
    x,y=map(int,input().split())
    point.append([x,y])
p=0
q=0
point.sort()
ans=0
for i in range(0,N-1):
    for j in range(i+1,N):
        p=point[j][0]-point[i][0]
        q=point[j][1]-point[i][1]
        merge=0
        for k in range(0,N):
            if([point[k][0]+p,point[k][1]+q] in point):
                merge+=1
        ans=max(ans,merge)
print(N-ans)

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
d = defaultdict(int)
for i in range(n):
    x1, y1 = xy[i]
    for j in range(i+1, n):
        x2, y2 = xy[j]
        d["%d:%d" % (x2-x1, y2-y1)] += 1

print(n-max(d.values()))


Fixed submission:
N=int(input())
point=[]
merge=0
for num in range(0,N):
    x,y=map(int,input().split())
    point.append([x,y])
p=0
q=0
point.sort()
ans=0
for i in range(0,N-1):
    for j in range(i+1,N):
        p=point[j][0]-point[i][0]
        q=point[j][1]-point[i][1]
        merge=0
        for k in range(0,N):
            if([point[k][0]+p,point[k][1]+q] in point):
                merge+=1
        ans=max(ans,merge)
print(N-ans)
Buggy python submission (verdict: Time Limit Exceeded):
h, w = map(int, input().split())
m = [input().strip() for _ in range(h)]

l = [[0] * w for _ in range(h)]
r = [[0] * w for _ in range(h)]
u = [[0] * w for _ in range(h)]
d = [[0] * w for _ in range(h)]

for y in range(h):
    for x in range(w):
        dy = y
        uy = h - y - 1
        if m[dy][x] == '.':
            if dy == 0:
                d[dy][x] = 1
            else:
                d[dy][x] = d[dy - 1][x] + 1
        if m[uy][x] == '.':
            if uy == (h - 1):
                u[uy][x] = 1
            else:
                u[uy][x] = u[uy + 1][x] + 1

        lx = x
        rx = w - x - 1
        if m[y][lx] == '.':
            if lx == 0:
                l[y][lx] = 1
            else:
                l[y][lx] = l[y][lx - 1] + 1
        if m[y][rx] == '.':
            if rx == (w - 1):
                r[y][rx] = 1
            else:
                r[y][rx] = r[y][rx + 1] + 1

ans = 0
for y in range(h):
    for x in range(w):
        t = l[y][x] + r[y][x] + u[y][x] + d[y][x] - 3
        if t > ans:
            ans = t
print(ans)

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

l = [[0] * w for _ in range(h)]
r = [[0] * w for _ in range(h)]
u = [[0] * w for _ in range(h)]
d = [[0] * w for _ in range(h)]

for y in range(h):
    for x in range(w):
        dy = y
        uy = h - y - 1
        if m[dy][x] == '.':
            if dy == 0:
                d[dy][x] = 1
            else:
                d[dy][x] = d[dy - 1][x] + 1
        if m[uy][x] == '.':
            if uy == (h - 1):
                u[uy][x] = 1
            else:
                u[uy][x] = u[uy + 1][x] + 1

        lx = x
        rx = w - x - 1
        if m[y][lx] == '.':
            if lx == 0:
                l[y][lx] = 1
            else:
                l[y][lx] = l[y][lx - 1] + 1
        if m[y][rx] == '.':
            if rx == (w - 1):
                r[y][rx] = 1
            else:
                r[y][rx] = r[y][rx + 1] + 1

ans = 0
for y in range(h):
    for x in range(w):
        t = l[y][x] + r[y][x] + u[y][x] + d[y][x] - 3
        if t > ans:
            ans = t
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
*A, = map(int, input().split())
BC = [list(map(int, input().split())) for _ in range(M)]
A.sort()
BC.sort(key=lambda v: -v[1])

ai = 0
for b, c in BC:
    while b > 0 and A[ai] < c:
        A[ai] = c
        b -= 1
        ai += 1

print(sum(A))

Fixed submission:
N, M = map(int, input().split())
*A, = map(int, input().split())
BC = [list(map(int, input().split())) for _ in range(M)]
A.sort()
BC.sort(key=lambda v: -v[1])

ai = 0
for b, c in BC:
    while b > 0 and ai < N and A[ai] < c:
        A[ai] = c
        b -= 1
        ai += 1

print(sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
from decimal import Decimal
N, K = map(int, input().split())
ans = 0
for n in range(1, N + 1):
    c = 0
    while n < K:
        n = n << 1
        c += 1
    t = 1 << c
    ans += Decimal("1.0") / Decimal(str(N * t))
print(ans)

Fixed submission:
from decimal import Decimal
N, K = map(int, input().split())
ans = 0
for n in range(1, N + 1):
    c = 0
    while n < K:
        n = n << 1
        c += 1
    t = 1 << c
    ans += Decimal("1.0") / Decimal(str(N * t))
print(ans)
Buggy python submission (verdict: Runtime Error):
class Node:
    def __init__(self, id, p, w):
        self.id = id
        self.w = w
        self.parent = p
        self.childs = []


N = int(input())
uvw = [list(map(int, input().split())) for _ in range(N - 1)]
nodes = [None for i in range(N + 1)]
nodes[1] = Node(1, None, 0)
for u, v, w in sorted(uvw):
    if nodes[u] != None:
        nodes[v] = Node(v, nodes[u], nodes[u].w + w)
        nodes[u].childs.append(nodes[v])
    elif nodes[v] != None:
        nodes[u] = Node(u, nodes[v], nodes[v].w + w)
        nodes[v].childs.append(nodes[u])

for node in nodes[1:]:
    print(node.w % 2)


Fixed submission:
from collections import deque


class Node:
    def __init__(self, id, w):
        self.id = id
        self.w = w


N = int(input())
uvw = [list(map(int, input().split())) for _ in range(N - 1)]
pairs = [[] for _ in range(N + 1)]
for u, v, w in uvw:
    pairs[u].append([v, w])
    pairs[v].append([u, w])

nodes = {1: Node(1, 0)}
q = deque([nodes[1]])
while len(q) > 0:
    node = q.pop()
    for v, w in pairs[node.id]:
        if v not in nodes:
            nodes[v] = Node(v, node.w + w)
            q.append(nodes[v])

for i in range(1, N + 1):
    print(nodes[i].w % 2)
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
h = {}
c = {}
for i in range(N):
    h[i + 1] = []
    c[i + 1] = 0

for m in range(M):
    x, y, z = map(int, input().split())
    h[x].append(y)
    h[y].append(x)

ans = 0
rest = N

while len(h) > 0:
    p = max([[len(v), k] for k, v in h.items()])
    if p[0] == 0:
        break
    rest = rest - p[0] - 1
    for n in h[p[1]]:
        del h[n]
    del h[p[1]]
    ans += 1

print(ans + rest)


Fixed submission:
from collections import defaultdict


class UnionFindTree:
    def __init__(self):
        self.p = {}
        self.rank = {}

    def make(self, x):
        self.p[x] = x
        self.rank[x] = 0

    def find(self, x):
        if x in self.p:
            if self.p[x] != x:
                # 経路圧縮
                self.p[x] = self.find(self.p[x])
            return self.p[x]
        return None

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def unite(self, x, y):
        return self._unite(self.find(x), self.find(y))

    def _unite(self, x, y):
        if self.rank[x] < self.rank[y]:
            self.p[x] = y
            return y
        else:
            self.p[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            return x


utf = UnionFindTree()

N, M = map(int, input().split())
for n in range(N):
    utf.make(n + 1)

for m in range(M):
    x, y, z = map(int, input().split())
    utf.unite(x, y)

h = defaultdict(int)
for n in range(N):
    x = utf.find(n + 1)
    h[x] += 1

ans = 0
rest = N
for k, v in h.items():
    ans += 1
    rest -= v
print(ans + rest)
Buggy python submission (verdict: Runtime Error):
import math
N = int(input())

ans = 0
for m in range(1, int(math.sqrt(N)) + 2):
    if (N - m) % m == 0:
        t = (N - m) // m
        a = N // t
        b = N % t
        if a == b:
            ans += t
print(ans)


Fixed submission:
import math
N = int(input())

ans = 0
for m in range(1, int(math.sqrt(N))+2):
    if N % m == 0:
        t = N//m - 1
        if t <= 0:
            continue
        a = N//t
        b = N % t
        if a == b:
            ans += t
print(ans)

Buggy python submission (verdict: Runtime Error):
import math
N = int(input())

ans = 0
for m in range(1, int(math.sqrt(N)) + 2):
    if (N - m) % m == 0:
        t = (N - m) // m
        a = N // t
        b = N % t
        if a == b:
            ans += t
print(ans)


Fixed submission:
import math
N = int(input())

ans = 0
for m in range(1, int(math.sqrt(N))+2):
    if N % m == 0:
        t = N//m - 1
        if t <= 0:
            continue
        a = N//t
        b = N % t
        if a == b:
            ans += t
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import fractions


def gcd(l, t):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a <= t:
            break
    return a


N = int(input())
*A, = map(int, input().split())
A.sort()
ans = 1
for i in range(N):
    b = A[:i]+A[i+1:]
    g = gcd(b, ans)
    if g > ans:
        ans = g
print(ans)


Fixed submission:
import fractions


def gcd(l, t):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a <= t:
            break
    return a


N = int(input())
*A, = map(int, input().split())
A.sort()

dp = [[1]*N for i in range(2)]
dp[0][0] = A[0]

a, b = A[0], A[-1]
for i in range(1, N):
    a = fractions.gcd(a, A[i])
    dp[0][i] = a
    b = fractions.gcd(b, A[N-i])
    dp[1][N-i] = b

ans = 1
for i in range(N):
    g = 1
    if i == 0:
        g = dp[1][1]
    elif i == (N-1):
        g = dp[0][-2]
    else:
        g = fractions.gcd(dp[0][i-1], dp[1][i+1])
    if g > ans:
        ans = g
print(ans)

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


def gcd(l):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a == 1:
            break
    return a


N = int(input())
*A, = map(int, input().split())
A.sort()
ans = 0
for i in range(N):
    b = A[:i]+A[i+1:]
    g = gcd(b)
    if g > ans:
        ans = g
print(ans)


Fixed submission:
import fractions


def gcd(l, t):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a <= t:
            break
    return a


N = int(input())
*A, = map(int, input().split())
A.sort()

dp = [[1]*N for i in range(2)]
dp[0][0] = A[0]

a, b = A[0], A[-1]
for i in range(1, N):
    a = fractions.gcd(a, A[i])
    dp[0][i] = a
    b = fractions.gcd(b, A[N-i])
    dp[1][N-i] = b

ans = 1
for i in range(N):
    g = 1
    if i == 0:
        g = dp[1][1]
    elif i == (N-1):
        g = dp[0][-2]
    else:
        g = fractions.gcd(dp[0][i-1], dp[1][i+1])
    if g > ans:
        ans = g
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import fractions
from functools import reduce


def gcd(numbers):
    return reduce(fractions.gcd, numbers)


N = int(input())
*A, = map(int, input().split())
ans = 0
for i in range(N):
    b = A[:i]+A[i+1:]
    g = gcd(b)
    if g > ans:
        ans = g
print(ans)


Fixed submission:
import fractions


def gcd(l, t):
    a = l.pop(0)
    for v in l:
        a = fractions.gcd(a, v)
        if a <= t:
            break
    return a


N = int(input())
*A, = map(int, input().split())
A.sort()

dp = [[1]*N for i in range(2)]
dp[0][0] = A[0]

a, b = A[0], A[-1]
for i in range(1, N):
    a = fractions.gcd(a, A[i])
    dp[0][i] = a
    b = fractions.gcd(b, A[N-i])
    dp[1][N-i] = b

ans = 1
for i in range(N):
    g = 1
    if i == 0:
        g = dp[1][1]
    elif i == (N-1):
        g = dp[0][-2]
    else:
        g = fractions.gcd(dp[0][i-1], dp[1][i+1])
    if g > ans:
        ans = g
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
a = [0]*n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        a[i] = 1

for i in range(q):
    l, r = map(int, input().split())
    lr = s[l-1:r]
    print(sum(a[l-1:r-1]))


Fixed submission:
n, q = map(int, input().split())
s = input()
a = [0]*n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        a[i+1] = 1
    if i > 0:
        a[i] += a[i-1]
a[n-1] += a[n-2]

for i in range(q):
    l, r = map(int, input().split())
    t = a[r-1]-a[l-1]
    print(t)

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
for i in range(q):
    l, r = map(int, input().split())
    lr = s[l-1:r]
    ans = 0
    for j in range(len(lr)-1):
        if lr[j:j+2] == 'AC':
            ans += 1
    print(ans)

Fixed submission:
n, q = map(int, input().split())
s = input()
a = [0]*n
for i in range(n-1):
    if s[i:i+2] == 'AC':
        a[i+1] = 1
    if i > 0:
        a[i] += a[i-1]
a[n-1] += a[n-2]

for i in range(q):
    l, r = map(int, input().split())
    t = a[r-1]-a[l-1]
    print(t)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
ab.sort()

ans = 0
m = 0
while m < M:
    a, b = ab.pop(0)
    tm = min([b, M - m])
    ans += tm * a
    m += tm
print(ans)

Fixed submission:
from collections import deque
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
ab.sort()

ab = deque(ab)

ans = 0
m = 0
while m < M:
    a, b = ab.popleft()
    tm = min([b, M - m])
    ans += tm * a
    m += tm
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
*h, = map(int, input().split())

dp = [0] * N
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
    c = 10**10
    for j in range(i - 1, max(i - K - 1, -1), -1):
        t = abs(h[j] - h[i]) + dp[j]
        if t < c:
            c = t
    dp[i] = c
print(dp[N - 1])


Fixed submission:
N, K = map(int, input().split())
*h, = map(int, input().split())

dp = [0] * N
dp[1] = abs(h[1] - h[0])
for i in range(2, N):
    c = 10**10
    for j in range(i - 1, max(i - K - 1, -1), -1):
        t = abs(h[j] - h[i]) + dp[j]
        if t < c:
            c = t
    dp[i] = c
print(dp[N - 1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
abc.append([0, 0, 0])

dp = [[-1] * 4 for i in range(N + 1)]


def happy(n, p):
    if n < 0:
        return 0
    if dp[n][p] >= 0:
        return dp[n][p]

    a = 0 if p == 0 else happy(n - 1, 0) + abc[n][0]
    b = 0 if p == 1 else happy(n - 1, 1) + abc[n][1]
    c = 0 if p == 2 else happy(n - 1, 2) + abc[n][2]
    dp[n][p] = max([a, b, c])

    return dp[n][p]


print(happy(N - 1, 3))


Fixed submission:
import sys
sys.setrecursionlimit(10**8)

N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
abc.append([0, 0, 0])

dp = [[-1] * 4 for i in range(N + 1)]


def happy(n, p):
    if n < 0:
        return 0
    if dp[n][p] >= 0:
        return dp[n][p]

    a = 0 if p == 0 else happy(n - 1, 0) + abc[n][0]
    b = 0 if p == 1 else happy(n - 1, 1) + abc[n][1]
    c = 0 if p == 2 else happy(n - 1, 2) + abc[n][2]
    dp[n][p] = max([a, b, c])

    return dp[n][p]


print(happy(N - 1, 3))

Buggy python submission (verdict: Runtime Error):
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
abc.append([0, 0, 0])

dp = [[-1] * 4 for i in range(N + 1)]


def happy(n, p):
    if n < 0:
        return 0
    if dp[n][p] >= 0:
        return dp[n][p]

    a = 0 if p == 0 else happy(n - 1, 0) + abc[n][0]
    b = 0 if p == 1 else happy(n - 1, 1) + abc[n][1]
    c = 0 if p == 2 else happy(n - 1, 2) + abc[n][2]
    dp[n][p] = max([a, b, c])

    return dp[n][p]


print(happy(N - 1, 3))


Fixed submission:
import sys
sys.setrecursionlimit(10**8)

N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
abc.append([0, 0, 0])

dp = [[-1] * 4 for i in range(N + 1)]


def happy(n, p):
    if n < 0:
        return 0
    if dp[n][p] >= 0:
        return dp[n][p]

    a = 0 if p == 0 else happy(n - 1, 0) + abc[n][0]
    b = 0 if p == 1 else happy(n - 1, 1) + abc[n][1]
    c = 0 if p == 2 else happy(n - 1, 2) + abc[n][2]
    dp[n][p] = max([a, b, c])

    return dp[n][p]


print(happy(N - 1, 3))

Buggy python submission (verdict: Runtime Error):
N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
abc.append([0, 0, 0])

dp = [[-1] * 4 for i in range(N + 1)]
print(dp)


def happy(n, p):
    if n < 0:
        return 0
    if dp[n][p] >= 0:
        return dp[n][p]

    a = 0 if p == 0 else happy(n - 1, 0) + abc[n][0]
    b = 0 if p == 1 else happy(n - 1, 1) + abc[n][1]
    c = 0 if p == 2 else happy(n - 1, 2) + abc[n][2]
    dp[n][p] = max([a, b, c])

    return dp[n][p]


print(happy(N - 1, 3))


Fixed submission:
import sys
sys.setrecursionlimit(10**8)

N = int(input())
abc = [list(map(int, input().split())) for i in range(N)]
abc.append([0, 0, 0])

dp = [[-1] * 4 for i in range(N + 1)]


def happy(n, p):
    if n < 0:
        return 0
    if dp[n][p] >= 0:
        return dp[n][p]

    a = 0 if p == 0 else happy(n - 1, 0) + abc[n][0]
    b = 0 if p == 1 else happy(n - 1, 1) + abc[n][1]
    c = 0 if p == 2 else happy(n - 1, 2) + abc[n][2]
    dp[n][p] = max([a, b, c])

    return dp[n][p]


print(happy(N - 1, 3))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

N,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(N)]

dp=[[-1]*(W+1) for i in range(N+1)]

def calc(n,w):
    if n<0:
        return 0
    if dp[n][w]>=0:
        return dp[n][w]
    cw,cv=wv[n]
    r1,r2=0,0
    r1=calc(n-1,w)
    if (cw+w)<=W:
        r2=calc(n-1,cw+w)+cv

    dp[n][w]= max([r1,r2])
    return dp[n][w]

print(calc(N-1,0))

Fixed submission:
import sys
sys.setrecursionlimit(10**8)

N,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(N)]

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

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

print(dp[N][W])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

N,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(N)]

dp=[[-1]*(W+1) for i in range(N+1)]

def calc(n,w):
    if n<0:
        return 0
    if dp[n][w]>=0:
        return dp[n][w]
    cw,cv=wv[n]
    r1,r2=0,0
    r1=calc(n-1,w)
    if (cw+w)<=W:
        r2=calc(n-1,cw+w)+cv

    return max([r1,r2])

print(calc(N-1,0))

Fixed submission:
import sys
sys.setrecursionlimit(10**8)

N,W=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(N)]

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

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

print(dp[N][W])