Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from sys import argv
import time
np.random.seed(1)


def input_from_file():
    with open(argv[1], "r") as f:
        D = int(f.readline())
        C = np.array(f.readline().split(), dtype=int)
        S = tuple(tuple(map(int, f.readline().split())) for _ in range(D))
    return D, C, S


def input_from_console():
    D = int(input())
    C = np.array(input().split(), dtype=int)
    S = tuple(tuple(map(int, input().split())) for _ in range(D))
    return D, C, S


def greed(D, C, S):
    last = np.ones(26, dtype=int)
    ans = []
    for s in S:
        s = np.array(s)
        tmp = s + C * last
        i = np.argmax(tmp)
        last[i] = 0
        last += 1
        ans.append(i + 1)
    return ans


def calc_score(D, C, S, T):
    res = 0
    last = np.ones(26, dtype=int)
    for d, t in enumerate(T):
        t -= 1
        last[t] = 0
        score = S[d][t]
        score -= (C * last).sum()
        res += score
        last += 1
    return res


def main():
    start = time.time()
    lim = 1.900
    D, C, S = input_from_console()
    #D, C, S = input_from_file()
    #初期解, 貪欲法
    sol = greed(D, C, S)
    score = calc_score(D, C, S, sol)
    while True:
        d = np.random.randint(0, D)
        q = np.random.randint(1, 27)
        old = sol[d]
        sol[d] = q
        new_score = calc_score(D, C, S, sol)
        if new_score > score:
            score = new_score
        else:
            sol[d] = old
        if time.time() - start >= lim:
            break
    print(*sol, sep="\n")


if __name__ == "__main__":
    main()

Fixed submission:
import numpy as np
D = int(input())
C = np.array(input().split(), dtype=int)
S = tuple(tuple(map(int, input().split())) for _ in range(D))

last = np.ones(26, dtype=int)

for s in S:
    s = np.array(s)
    tmp = s + C * last
    i = np.argmax(tmp)
    last[i] = 0
    last += 1
    print(i + 1)
Buggy python submission (verdict: Time Limit Exceeded):

def sieve_eratosthenes(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return [i for i, p in enumerate(primes) if p]


def main():
    N = int(input())
    prime = sieve_eratosthenes(N + 1)

    X = [i for i in range(N + 1)]
    cnt = [1] * (N + 1)
    for p in prime:
        for i in range(p, N + 1, p):
            tmp = 0
            while X[i] % p == 0:
                tmp += 1
                X[i] //= p
            cnt[i] *= tmp + 1

    ans = sum(i * x for i, x in enumerate(cnt[1:], 1))
    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
N = int(input())
ans = 0

for i in range(1, N + 1):
    n = N // i
    ans += i * n * (n + 1) // 2

print(ans)
Buggy python submission (verdict: Runtime Error):
N = input()
N = int(N[-1])
if N == 3:
    print("bon")
elif N in [0, 1, 6, 8]:
    print("pon")
else:
    p

Fixed submission:
def maiin(S):
    N = int(S[-1])

    if N == 3:
        print("bon")
    elif N in [0, 1, 6, 8]:
        print("pon")
    else:
        print("hon")

if __name__ == "__main__":
    maiin(input())
Buggy python submission (verdict: Time Limit Exceeded):
import networkx as nx
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


G = nx.Graph()
N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]
G.add_edges_from(edge)
path = nx.single_source_shortest_path(G, source=1)

print("Yes")
for i in range(2, N + 1):
    print(path[i][-2])

Fixed submission:
from collections import deque
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

prev = [None] * (N + 1)
seen = [False] * (N + 1)
node = deque([1])
seen[1] = True

while node:
    s = node.popleft()
    for t in edge[s]:
        if not seen[t]:
            seen[t] = True
            prev[t] = s
            node.append(t)

if any(x is None for x in prev[2:]):
    print("No")
else:
    print("Yes")
    print(*prev[2:], sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
import networkx as nx
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


G = nx.Graph()
N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]
G.add_edges_from(edge)
path = nx.shortest_path(G, source=1)

print("Yes")
for i in range(2, N + 1):
    print(path[i][-2])

Fixed submission:
from collections import deque
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

prev = [None] * (N + 1)
seen = [False] * (N + 1)
node = deque([1])
seen[1] = True

while node:
    s = node.popleft()
    for t in edge[s]:
        if not seen[t]:
            seen[t] = True
            prev[t] = s
            node.append(t)

if any(x is None for x in prev[2:]):
    print("No")
else:
    print("Yes")
    print(*prev[2:], sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
D = K.bit_length()
to = [[0] * D for _ in range(N)]

for i, a in enumerate(map(int, input().split())):
    to[i][0] = a - 1

for j in range(D - 1):
    for i in range(N):
        h = to[i][j]
        to[i][j+1] = to[h][j]

v = 0
for i in reversed(range(D)):
    x = 1 << i
    if x <= K:
        v = to[v][i]
        K -= x

print(v + 1)

Fixed submission:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

first = [0] * (N + 1)
second = [0] * (N + 1)
roop1 = []
roop2 = []

now = 1
while True:
    if not first[now]:
        first[now] = 1
        roop1.append(now)
        now = A[now]
    elif not second[now]:
        second[now] = 1
        roop2.append(now)
        now = A[now]
    else:
        break


if K < len(roop1):
    print(roop1[K])
else:
    K -= len(roop1)
    m = K % len(roop2)
    print(roop2[m])

Buggy python submission (verdict: Runtime Error):
D = 60
U = 2 * 10 ** 5 + 10
to = [[0] * D for _ in range(U)]

N, K = map(int, input().split())
for i, a in enumerate(map(int, input().split())):
    to[0][i] = a - 1
# 表の構築
for i in range(D - 1):
    for j in range(N):
        to[i + 1][j] = to[i][to[i][j]]

v = 0
for i in reversed(range(D)):
    x = 1 << i
    if x <= K:
        v = to[i][v]
        K -= x

print(v + 1)

Fixed submission:
N, K = map(int, input().split())
A = [0] + list(map(int, input().split()))

first = [0] * (N + 1)
second = [0] * (N + 1)
roop1 = []
roop2 = []

now = 1
while True:
    if not first[now]:
        first[now] = 1
        roop1.append(now)
        now = A[now]
    elif not second[now]:
        second[now] = 1
        roop2.append(now)
        now = A[now]
    else:
        break


if K < len(roop1):
    print(roop1[K])
else:
    K -= len(roop1)
    m = K % len(roop2)
    print(roop2[m])
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
from itertools import product, combinations
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

cand = [[1]]
for i in range(M-1):
    tmp = []
    while cand:
        x = cand.pop()
        for i in range(x[-1], M + 1):
            tmp.append(x + [i])
    cand = tmp

ans = 0
for X in cand:
    score = 0
    for a, b, c, d in abcd:
        if X[b - 1] - X[a - 1] == c:
            score += d
    ans = max(ans, score)
print(ans)

Fixed submission:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

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

cand = [[1]]
for i in range(N-1):
    tmp = []
    while cand:
        x = cand.pop()
        for i in range(x[-1], M + 1):
            tmp.append(x + [i])
    cand = tmp

ans = 0
for X in cand:
    score = 0
    for a, b, c, d in abcd:
        if X[b - 1] - X[a - 1] == c:
            score += d
    ans = max(ans, score)
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
N, X, Y = map(int, input())
edge = [[] for _ in range(N)]
for i in range(N - 1):
    edge[i].append(i + 1)
    edge[i + 1].append(i)
edge[X-1].append(Y-1)
edge[Y-1].append(X-1)

cnt = [0] * (N - 1)


def search(i):
    node = deque([i])
    seen = [-1] * N
    seen[i] = 0

    while node:
        s = node.popleft()
        d = seen[s]
        for t in edge(s):
            if seen[t] == -1:
                seen[t] = d + 1
                if s < t:
                    cnt[d] += 1
                node.append(t)


for i in range(N - 1):
    search(i)
print(*cnt, sep="\n")

Fixed submission:
from scipy.sparse.csgraph import dijkstra
import numpy as np
N, X, Y = map(int, input().split())
X -= 1
Y -= 1

g = np.zeros((N, N), dtype=int)
a = np.arange(N - 1)
np.add.at(g, (a, a + 1), 1)
np.add.at(g, (a + 1, a), 1)
np.add.at(g, (X, Y), 1)
np.add.at(g, (Y, X), 1)
fw = dijkstra(g, directed=False)
fw = (fw + 0.5).astype(int)
fw = np.tril(fw).ravel()
fw = fw[fw > 0]

cnt = np.bincount(fw).tolist()
ans = [0] * (N - 1)
for i, c in enumerate(cnt[1:]):
    ans[i] = c

print(*ans, sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
N, X, Y = map(int, input().split())
X -= 1
Y -= 1

g = np.zeros((N, N), dtype=int)
a = np.arange(N - 1)
np.add.at(g, (a, a + 1), 1)
np.add.at(g, (a + 1, a), 1)
np.add.at(g, (X, Y), 1)
np.add.at(g, (Y, X), 1)
fw = floyd_warshall(g)
fw = (fw + 0.5).astype(int)
fw = np.tril(fw).ravel()
fw = fw[fw > 0]

cnt = np.bincount(fw).tolist()
ans = [0] * (N - 1)
for i, c in enumerate(cnt[1:]):
    ans[i] = c

print(*ans, sep="\n")

Fixed submission:
from scipy.sparse.csgraph import dijkstra
import numpy as np
N, X, Y = map(int, input().split())
X -= 1
Y -= 1

g = np.zeros((N, N), dtype=int)
a = np.arange(N - 1)
np.add.at(g, (a, a + 1), 1)
np.add.at(g, (a + 1, a), 1)
np.add.at(g, (X, Y), 1)
np.add.at(g, (Y, X), 1)
fw = dijkstra(g, directed=False)
fw = (fw + 0.5).astype(int)
fw = np.tril(fw).ravel()
fw = fw[fw > 0]

cnt = np.bincount(fw).tolist()
ans = [0] * (N - 1)
for i, c in enumerate(cnt[1:]):
    ans[i] = c

print(*ans, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
import numpy as np
H, W, K = map(int, input().split())
choko = np.array([list(input()) for _ in range(H)], dtype=int)

np.cumsum(choko, axis=1, out=choko)

ans = 10**18
for p in product(range(2), repeat=H - 1):
    Hcut = sum(p)

    ch = np.zeros((Hcut + 1, W), dtype=int)
    cnt = choko[0]
    h = 0
    for i, b in enumerate(p):
        if b:
            ch[h] = cnt
            cnt = choko[i + 1]
            h += 1
        else:
            cnt = cnt + choko[i + 1]
    ch[h] = cnt

    if (ch[:, 0] > K).any():
        continue

    Vcut = 0
    left = np.zeros(Hcut + 1, dtype=int)
    for i in range(W):
        right = ch[:, i]
        if (right - left > K).any():
            Vcut += 1
            left = ch[:, i - 1]
    ans = min(ans, Hcut + Vcut)

print(ans)

Fixed submission:
from itertools import product, combinations_with_replacement
H, W, K = map(int, input().split())
S = tuple(tuple(map(int, list(input()))) for _ in range(H))

choko = [[0]*W for _ in range(H)]

ans = 10**18

for divide in product(range(2), repeat=H - 1):
    cut = sum(divide)
    row = [0]
    for d in divide:
        if d:
            row.append(row[-1] + 1)
        else:
            row.append(row[-1])

    r = row[-1] + 1
    for i in range(r):
        for j in range(W):
            choko[i][j] = 0
    for i in range(H):
        for j in range(W):
            choko[row[i]][j] += S[i][j]

    if any(choko[i][0] > K for i in range(r)):
        continue

    now = [0] * r
    for j in range(W):
        if any(now[i] + choko[i][j] > K for i in range(r)):
            cut += 1
            now = [choko[i][j] for i in range(r)]
        else:
            for i in range(r):
                now[i] += choko[i][j]

    ans = min(ans, cut)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N, P = map(int, input().split())
S = input()

ans = 0
if P == 2:
    for i, s in enumerate(S, start=1):
        if int(s) % 2 == 0:
            ans += i
elif P == 5:
    for i, s in enumerate(S, start=1):
        if s in "05":
            ans += i
else:
    T = [0] * (N+1)
    d = 0
    for i, s in enumerate(S[::-1], start=1):
        s = int(s) * (10 ** d) + T[i - 1]
        T[i] = s % P
        d += 1
    c = Counter(T)
    ans = sum(x * (x - 1) // 2 for x in c.values())

print(ans)


Fixed submission:
from collections import Counter
N, P = map(int, input().split())
S = input()

ans = 0
if P == 2:
    for i, s in enumerate(S, start=1):
        if int(s) % 2 == 0:
            ans += i
elif P == 5:
    for i, s in enumerate(S, start=1):
        if s in "05":
            ans += i
else:
    T = [0] * (N+1)
    d = 1
    for i, s in enumerate(S[::-1], start=1):
        s = int(s) * d + T[i - 1]
        T[i] = s % P
        d *= 10
        d %= P
    c = Counter(T)
    ans = sum(x * (x - 1) // 2 for x in c.values())

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
d = defaultdict(list)

N, M = map(int, input().split())
for _ in range(M):
    s, c = map(int, input().split())
    d[s].append(c)

ans = [-1] * N

# とりあえず桁を確定させる
for k, v in d.items():
    if len(set(v)) > 1:
        print(-1)
        exit()
    ans[k - 1] = v[0]

if N == 1:
    val = ans.pop()
    val = max(0, val)
else:
    val = ""
    for i, a in enumerate(ans):
        if a != -1:
            val += str(a)
        else:
            if i == 0:
                val += "1"
            else:
                val += "0"

if val[0] == "0":
    print(-1)
    exit()

print(val)


Fixed submission:
from collections import defaultdict
d = defaultdict(list)

N, M = map(int, input().split())
for _ in range(M):
    s, c = map(int, input().split())
    d[s].append(c)

val = [-1] * N

# とりあえず桁を確定させる
for k, v in d.items():
    if len(set(v)) > 1:
        print(-1)
        exit()
    val[k - 1] = v[0]

if N == 1:
    ans = max(0, val.pop())
    print(ans)
    exit()
if N >= 2:
    if val[0] == 0:
        print(-1)
        exit()

    if val[0] == -1:
        val[0] = 1
    for i in range(N):
        val[i] = max(0, val[i])

    print(*val, sep="")
Buggy python submission (verdict: Time Limit Exceeded):
class BinaryIndexTree:  # 1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


if __name__ == "__main__":
    N = int(input())
    S = list(input())
    d = {x: i for i, x in enumerate("abcdefghijklmnopqrstuvwxyz")}
    BIT = [BinaryIndexTree(N) for _ in range(26)]

    # initialize
    for i, s in enumerate(S, start=1):
        BIT[d[s]].add(i, 1)

    Q = int(input())
    ans = []
    for _ in range(Q):
        query, x, y = input().split()
        if query == "1":
            i = int(x)
            c_new = y
            c_old = S[i - 1]
            BIT[d[c_new]].add(i, 1)
            BIT[d[c_old]].add(i, -1)
            S[i - 1] = c_new
        else:
            cnt = 0
            l = int(x) - 1
            r = int(y)
            for b in BIT:
                tmp = b.sum(r) - b.sum(l)
                if tmp:
                    cnt += 1
            ans.append(cnt)

    print(*ans, sep="\n")


Fixed submission:
class BinaryIndexTree:  # 1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


if __name__ == "__main__":
    N = int(input())
    S = list(input())
    d = {x: i for i, x in enumerate("abcdefghijklmnopqrstuvwxyz")}
    BIT = [BinaryIndexTree(N) for _ in range(26)]

    # initialize
    for i, s in enumerate(S, start=1):
        BIT[d[s]].add(i, 1)

    Q = int(input())
    ans = []
    for _ in range(Q):
        query, x, y = input().split()
        if query == "1":
            i = int(x)
            c_new = y
            c_old = S[i - 1]
            BIT[d[c_new]].add(i, 1)
            BIT[d[c_old]].add(i, -1)
            S[i - 1] = c_new
        else:
            cnt = 0
            l = int(x) - 1
            r = int(y)
            for b in BIT:
                tmp = b.sum(r) - b.sum(l)
                if tmp:
                    cnt += 1
            ans.append(cnt)

    print(*ans, sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
import numpy as np
MOD = 10 ** 9 + 7


def cumprod(A, mod=MOD):
    L = len(A)
    Lsq = int(L ** 0.5 + 1)
    A = np.resize(A, Lsq ** 2).reshape((Lsq, Lsq))
    for i in range(1, Lsq):
        A[:, i] *= A[:, i - 1]
        A[:, i] %= mod
    for i in range(1, Lsq):
        A[i] *= A[i - 1][-1]
        A[i] %= mod
    return A.ravel()[:L]


def make_fact_and_inv(U, mod=MOD):
    """
    0~Nまでのサイズ(N+1)の階乗およびその逆元の配列を返す
    """
    tmp = np.arange(U, dtype=np.int64)
    tmp[0] = 1
    fact = cumprod(tmp, mod)
    tmp = np.arange(U, 0, -1, dtype=np.int64)
    tmp[0] = pow(int(fact[-1]), mod - 2, mod)
    inv = cumprod(tmp, mod)[::-1]
    return fact, inv


fact, inv = make_fact_and_inv(2 * 10 ** 6)


def nCr(n, r, mod=MOD):
    if r < 0 or r > n or n < 0:
        return 0
    return fact[n] * inv[r] % mod * inv[n - r] % mod


if __name__ == "__main__":
    N, K = map(int, input().split())

    ans = []
    for i in range(min(N - 1, K) + 1):
        val = nCr(N, i) * nCr(N - 1, i) % MOD
        ans.append(val)

    answer = 0
    while ans:
        answer = (answer + ans.pop()) % MOD
    print(answer)


Fixed submission:
N, K = map(int, input().split())
mod = 10 ** 9 + 7

K = min(K, N - 1)

fact = [1]
facinv = [1]
for i in range(1, N + 1):
    fact.append(fact[-1]*i % mod)


def nCr(n, r):
    num = fact[n]
    div = fact[r] * fact[n - r] % mod
    return num * pow(div, mod - 2, mod) % mod


move = [0] * (N + 1)
move[0] = 1
for i in range(1, N + 1):
    x = nCr(N, i) * nCr(N - 1, N - i - 1) % mod
    move[i] = x

for i in range(1, N):
    move[i] = (move[i - 1] + move[i]) % mod

ans = move[K]
print(ans)
Buggy python submission (verdict: Runtime Error):
import bisect
import numpy as np
N, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
A = np.sort(A)

Aneg = A[A < 0]
Azero = A[A == 0]
Apos = A[A > 0]

neg = len(Aneg)
zero = len(Azero)
pos = len(Apos)

Nneg = neg * pos
Npos = 0
if neg > 0:
    Npos += neg * (neg - 1) // 2
if pos > 0:
    Npos += pos * (pos - 1) // 2
Nzero = N * (N - 1) // 2 - Npos - Nneg
print(Nneg, Npos, Nzero)


def C(N, ar):
    if len(ar) <= 1:
        return 0
    tmp = np.arange(len(ar))+1
    n = np.searchsorted(ar, N / ar, side="left")
    return (len(ar)-np.maximum(n, tmp)).sum()


def C1(N, ar1, ar2):
    tmp = np.arange(len(ar1))+1
    n = np.searchsorted(ar1, N / ar2, side="left")
    return (len(ar1)-np.maximum(n, tmp)).sum()


def bs_Neg():
    l, r = -10 ** 20, 0
    while r - l > 1:
        m = (r - l) // 2
        num = C1(m, Apos, Aneg)
        if num < K:
            r = m
        else:
            l = m
    return l


def bs_Pos(K):
    l, r = 0, 10 ** 20
    while r - l > 1:
        m = (r - l) // 2
        num = C(m, Apos) + C(m, Aneg)
        if num < K:
            r = m
        else:
            l = m
    return l


if K <= Nneg:
    ans = bs_Neg()
elif K <= Nneg + Nzero:
    ans = 0
else:
    K = K-Nneg-Nzero
    ans = bs_Pos(K)

print(ans)


Fixed submission:
import numpy as np


def get_Negative(K, pos, neg):
    K = len(pos) * len(neg) - K + 1
    l = 0
    r = 10 ** 18 + 10
    while r - l > 1:
        m = (l + r) // 2
        target = m // pos
        x = np.searchsorted(neg, target, side="right").sum()
        if x >= K:
            r = m
        else:
            l = m
    return -r


def get_Positive(K, pos, neg):
    l = 0
    r = 10 ** 18 + 10
    tmp_pos = np.arange(len(pos))
    tmp_neg = np.arange(len(neg))
    while r - l > 1:
        m = (r + l) // 2
        cnt = 0
        if len(pos) > 1:
            t1 = m // pos
            x1 = np.searchsorted(pos, t1, side="right")
            x1 = np.maximum(0, x1 - tmp_pos - 1)
            cnt += x1.sum()
        if len(neg) > 0:
            t2 = m // neg
            x2 = np.searchsorted(neg, t2, side="right")
            x2 = np.maximum(0, x2 - tmp_neg - 1)
            cnt += x2.sum()
        if cnt >= K:
            r = m
        else:
            l = m
    return r


def main():
    N, K = map(int, input().split())
    A = np.array(input().split(), dtype=np.int64)

    positive = A[A > 0]
    negative = -A[A < 0]
    positive.sort()
    negative.sort()

    Npos = len(positive)
    Nneg = len(negative)
    Nzero = N - Npos - Nneg

    P_neg = Npos * Nneg
    P_pos = 0
    if Npos:
        P_pos += Npos * (Npos - 1) // 2
    if Nneg:
        P_pos += Nneg * (Nneg - 1) // 2
    P_zero = N * (N - 1) // 2 - P_pos - P_neg

    if K <= P_neg:
        ans = get_Negative(K, positive, negative)
        return ans
    K -= P_neg
    if K <= P_zero:
        return 0
    K -= P_zero
    ans = get_Positive(K, positive, negative)
    return ans


if __name__ == "__main__":
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [10 ** 18] * (2 * 10 ** 4 + 1)
dp[0] = 0
for a, b in AB:
    for i in range(H):
        dp[i + a] = min(dp[i + a], dp[i] + b)

ans = min(dp[H:])
print(ans)


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

dp = [10 ** 18] * (2 * 10 ** 4 + 1)
dp[0] = 0
for a, b in AB:
    for i in range(H):
        dp[i + a] = min(dp[i + a], dp[i] + b)

ans = min(dp[H:])
print(ans)