Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
mod = int(1e9 + 7)
def powmod(a, b):
    ans = 1
    while(b):
        if(b&1): ans = ans*a%mod
        a = a*a%mod
        b >>= 1
    return ans
x, y = map(int,input().split())
if((2*x-y)%3 or (2*y-x)%3): print(0)
else:
    x, y = (2*x-y)//3, (2*y-x)//3
    #print(x,y)
    fac = [0 for i in range(x+y+1)]
    inv = [0 for i in range(x+y+1)]
    fac[0] = 1
    for i in range(1,x+y+1):
        fac[i] = fac[i-1]*i%mod
    inv[x+y] = powmod(fac[x+y],mod-2)
    for i in range(x+y-1,-1,-1):
        inv[i] = inv[i+1]*(i+1)%mod
    ans = fac[x+y]*inv[x]*inv[y]%mod
    print(ans)

Fixed submission:
mod = int(1e9 + 7)
def powmod(a, b):
    ans = 1
    while(b):
        if(b&1): ans = ans*a%mod
        a = a*a%mod
        b >>= 1
    return ans
x, y = map(int,input().split())
if(2*x < y or 2*y < x or (2*x-y)%3 or (2*y-x)%3): print(0)
else:
    x, y = (2*x-y)//3, (2*y-x)//3
    #print(x,y)
    fac = [0 for i in range(x+y+1)]
    inv = [0 for i in range(x+y+1)]
    fac[0] = 1
    for i in range(1,x+y+1):
        fac[i] = fac[i-1]*i%mod
    inv[x+y] = powmod(fac[x+y],mod-2)
    for i in range(x+y-1,-1,-1):
        inv[i] = inv[i+1]*(i+1)%mod
    ans = fac[x+y]*inv[x]*inv[y]%mod
    print(ans)
Buggy python submission (verdict: Runtime Error):
def gcd(a, b):
  while(b > 0):
    a %= b
    swap(a, b)
  return a
def lcm(a, b):
  return a * b // gcd(a,b)
n = int(input())
md = int(1e9 + 7)
a = [int(e) for e in input().split()]
x = 1
for j in range(n):
  x = lcm(x, a[j])
ans = 0
for i in range(n):
  ans += lcm // a[i]
ans %= md
print(ans)

Fixed submission:
def gcd(a, b):
  while(b > 0):
    a %= b
    a, b = b, a
  return a
def lcm(a, b):
  return a * b // gcd(a,b)
n = int(input())
md = int(1e9 + 7)
a = [int(e) for e in input().split()]
x = 1
for j in range(n):
  x = lcm(x, a[j])
ans = 0
for i in range(n):
  ans += x // a[i]
ans %= md
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[int(x) for x in input().split()]
x=1
bb=pow(10,18)
for i in range(n):
    x*=a[i]
if (x>bb):
    print(-1)
else:
    print(x)

Fixed submission:
n=int(input())
a=[int(x) for x in input().split()]
x=1
bb=pow(10,18)
for i in range(n):
    if (a[i]==0):
        print(0)
        exit()
for i in range(n):
    x*=a[i]
    if (x>bb):
        print(-1)
        exit()
print(x)
Buggy python submission (verdict: Runtime Error):
u = input()

a = u[0];
b = u[2];
at = int(a)
bt = int(b)

x = at*b
y = bt*a

if(x < y)
{
  print(x)
}
else
{
 print(y)
}

Fixed submission:
u = input()

a = u[0];
b = u[2];
at = int(a)
bt = int(b)

x = b*at
y = a*bt

if x <= y:
  print(x)

else:
 print(y)
Buggy python submission (verdict: Time Limit Exceeded):
def func(line):
    lp = 0
    res = ""
    while lp + 1 < len(line):
        if line[lp] != line[lp + 1]:
            lp += 2
        else:
            res += line[lp]
            lp += 1
    if lp == len(line) - 1:
        res += line[-1]
    return res


def main():
    line = input()
    startsize = len(line)
    while True:
        next = func(line)
        if len(line) == len(next):
            break
        line = next
    lastsize = len(line)
    print(startsize - lastsize)


if __name__ == "__main__":
    main()



Fixed submission:
def func(line):
    lp = 0
    res = []
    while lp < len(line):
        while len(res) > 0 and lp < len(line) and res[-1] != line[lp]:
            res.pop()
            lp += 1
        if lp < len(line):
            res.append(line[lp])
            lp += 1
    return res


def main():
    line = [i for i in input()]
    startsize = len(line)
    line = func(line)
    lastsize = len(line)
    print(startsize - lastsize)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N,Q = map(int, input().split())
L = [0]*Q
L1 = []
L2 = []
for i in range(Q):
    a,b = map(int, input().split())
    L[i] = (a, b)
    if a == 1:
        L1.append(b)
    else:
        L2.append(b)

L1.sort()
L2.sort()

ans = (N-2)**2
up = N
left = N
for l in L:
    a = l[0]
    b = l[1]
    if a == 1:
        if b > left:
            continue
        idx = bisect.bisect_left(L1, b)
        ans -= (len(L1)-idx)*(up-2)
        L1 = L1[:idx]
        left = b
    else:
        if b > up:
            continue
        idx = bisect.bisect_left(L2, b)
        ans -= (len(L2)-idx)*(left-2)
        L2 = L2[:idx]
        up = b
print(ans)

Fixed submission:
import bisect
N,Q = map(int, input().split())
L = [0]*Q
L1 = []
L2 = []
for i in range(Q):
    a,b = map(int, input().split())
    L[i] = (a, b)
    if a == 1:
        L1.append(b)
    else:
        L2.append(b)

L1.sort()
L2.sort()
M1 = len(L1)
M2 = len(L2)
ans = (N-2)**2
up = N
left = N
for l in L:
    a = l[0]
    b = l[1]
    if a == 1:
        if b > left:
            continue
        idx = bisect.bisect_left(L1, b)
        ans -= (M1-idx)*(up-2)
        M1 = idx
        left = b
    else:
        if b > up:
            continue
        idx = bisect.bisect_left(L2, b)
        ans -= (M2-idx)*(left-2)
        M2 = idx
        up = b
print(ans)
Buggy python submission (verdict: Runtime Error):
N,Q = map(int, input().split())
C = [int(c) for c in input().split()]

#区間の最大値を求めるセグメント木
seg = [0]*(2*N-1)
    
def update(k, x):
    k += N-1
    seg[k] = 1<<(x-1)
    while k:
        k = (k-1)//2
        seg[k] = (seg[2*k+1] & seg[2*k+2])
        
def query(p, q):
    p += N-1
    q += N-2
    res = 0
    while q-p > 1:
        if p&1 == 0:
            res = (res & seg[p])
        if q&1 == 1:
            res = (res & seg[q])
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res = (res & seg[q])
    else:
        res = (res & seg[p] & seg[q])
    return res


for i in range(N):
    update(i, C[i])

for _ in range(Q):
    l, r = map(int, input().split())
    print(query(l, r))

Fixed submission:
from operator import itemgetter
N,Q = map(int, input().split())
C = [int(c) for c in input().split()]
L = [[int(l) for l in input().split()] for _ in range(Q)]

for i in range(Q):
    L[i].append(i)
M = pow(2, len(bin(N))-2)
BIT = [0]*(M+1)
L.sort(key=itemgetter(1))
memo = [0]*(N+1)

ans = [0]*Q
i = 1
j = 0
while i <= N:
    c = C[i-1]
    idx = i
    if i <= L[j][1]:
        if memo[c] > 0:
            k = memo[c]
            while k <= M:
                BIT[k] -= 1
                k += k&(-k)
        memo[c] = i
        while idx <= M:
            BIT[idx] += 1
            idx += idx&(-idx)
    if i == L[j][1]:
        cnt = 0
        n = L[j][1]
        while n > 0:
            cnt += BIT[n]
            n -= n&(-n)
        n = L[j][0]-1
        while n > 0:
            cnt -= BIT[n]
            n -= n&(-n)
        ans[L[j][2]] = cnt
        j += 1
        if j == Q:
            break
        elif L[j][1] == i:
            i -= 1
    i += 1

for a in ans:
    print(a)
Buggy python submission (verdict: Time Limit Exceeded):
import copy
import time
import random

t1 = time.time()

def calc(T):
    res = 0
    L = [0]*26
    for i in range(D):
        res += S[i][T[i]-1]
        L[T[i]-1] = i+1
        for j in range(26):
            res -= C[j]*(i+1-L[j])
    return res
    
D = int(input())
C = [int(c) for c in input().split()]
S = [[int(s) for s in input().split()] for _ in range(D)]

T = [0]*D
for i in range(D):
    temp = -1
    for j in range(26):
        if temp < S[i][j]:
            temp = S[i][j]
            idx = j+1
    T[i] = idx

p = calc(T)

while time.time()-t1 < 1.9:
    i = random.randint(0, D-1)
    for j in range(26):
        temp = copy.deepcopy(T)
        temp[i] = j+1
        newp = calc(temp)
        if p < newp:
            T[i] = j+1
            p = newp

for t in T:
    print(t)

Fixed submission:
D = int(input())
C = [int(c) for c in input().split()]
S = [[int(s) for s in input().split()] for _ in range(D)]

T = [0]*D
for i in range(D):
    temp = -1
    for j in range(26):
        if temp < S[i][j]:
            temp = S[i][j]
            idx = j+1
    T[i] = idx

for t in T:
    print(t)

Buggy python submission (verdict: Runtime Error):
D = int(input())
C = [int(c) for c in input().split()]
S = [[int(s) for s in input().split()] for _ in range(D)]

T = [0]*26
for i in range(D):
    temp = -1
    for j in range(26):
        if temp < S[i][j]:
            temp = S[i][j]
            idx = j+1
    T[i] = idx

for t in T:
    print(t)

Fixed submission:
D = int(input())
C = [int(c) for c in input().split()]
S = [[int(s) for s in input().split()] for _ in range(D)]

T = [0]*D
for i in range(D):
    temp = -1
    for j in range(26):
        if temp < S[i][j]:
            temp = S[i][j]
            idx = j+1
    T[i] = idx

for t in T:
    print(t)
Buggy python submission (verdict: Time Limit Exceeded):
X = int(input())

x = [0]
y = [0]
t = X
ans = 1
while True:
    ans += 1
    x.append(t)
    y.append(t)
    if (180-t)%360 in x:
        if t == (180-t)%360 and x.count(t) == 1:
            t += X
            t %= 360
            continue
        x.remove((180-t)%360)
        x.remove(t)
    elif (180+t) in x:
        if t == (180+t)%360 and x.count(t) == 1:
            t += X
            t %= 360
            continue
        x.remove((180-t)%360)
        x.remove(t)
    if (-t)%360 in y:
        if t == (-t)%360 and y.count(t) == 1:
            t += X
            t %= 360
            continue
        y.remove((-t)%360)
        y.remove(t)
    elif (180+t) in y:
        if t == (180-t)%360 and y.count(t) == 1:
            t += X
            t %= 360
            continue
        y.remove((180-t)%360)
        y.remove(t)
    if len(x) == 0 and len(y) == 0:
        break
    t += X
    t %= 360
print(ans//2)

Fixed submission:
X = int(input())

ans = 360
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

ans = 360 // gcd(X, 360)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
X = int(input())

x = [0]
y = [0]
t = X
ans = 1
while True:
    ans += 1
    x.append(t)
    y.append(t)
    if (180-t)%360 in x:
        if t == (180-t)%360 and x.count(t) == 1:
            t += X
            t %= 360
            continue
        x.remove((180-t)%360)
        x.remove(t)
    elif (180+t) in x:
        if t == (180+t)%360 and x.count(t) == 1:
            t += X
            t %= 360
            continue
        x.remove((180-t)%360)
        x.remove(t)
    if (-t)%360 in y:
        if t == (-t)%360 and y.count(t) == 1:
            t += X
            t %= 360
            continue
        y.remove((-t)%360)
        y.remove(t)
    elif (180+t) in y:
        if t == (180-t)%360 and y.count(t) == 1:
            t += X
            t %= 360
            continue
        y.remove((180-t)%360)
        y.remove(t)
    if len(x) == 0 and len(y) == 0:
        break
    t += X
    t %= 360
print(ans//2)

Fixed submission:
X = int(input())

ans = 360
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

ans = 360 // gcd(X, 360)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(a) for a in input().split()]

M = 10**6+1
L = [0]*M

for a in A:
    if L[a] >= 1:
        L[a] = 2
        continue
    L[a] = 1
    i = 2
    while a*i <= M:
        L[a*i] = 2
        i += 1

ans = 0
for a in A:
    if L[a] == 1:
        ans += 1
print(ans)

Fixed submission:
N = int(input())
A = [int(a) for a in input().split()]

M = 10**6+1
L = [0]*M

for a in A:
    if L[a] >= 1:
        L[a] = 2
        continue
    L[a] = 1
    i = 2
    while a*i < M:
        L[a*i] = 2
        i += 1

ans = 0
for a in A:
    if L[a] == 1:
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())

p = [0]*10**6
for i in range(2, 10**6):
    if p[i] == 0:
        p[i] = 1
        j = 2
        while i*j < 10**6:
            p[i*j] = -1
            j += 1

L = []
ans = 0
for i in range(10**6):
    if p[i] < 1:
        continue
    j = 1
    while N%pow(i, j) == 0:
        L.append(pow(i, j))
        N //= pow(i, j)
        j += 1
        ans += 1

L2 = []
i = 2
while i <= N**0.5:
    if N%i == 0:
        L2.append(N, N//i)
    i += 1

if len(L2) == 0 and N > 1 and N not in L:
    ans += 1

print(ans)

Fixed submission:
N = int(input())

p = [0]*10**6
for i in range(2, 10**6):
    if p[i] == 0:
        p[i] = 1
        j = 2
        while i*j < 10**6:
            p[i*j] = -1
            j += 1

ans = 0
for i in range(10**6):
    if p[i] < 1:
        continue
    j = 1
    while N%pow(i, j) == 0:
        N //= pow(i, j)
        j += 1
        ans += 1

for i in range(10**6):
    if p[i] < 1:
        continue
    while N%i == 0:
        N //= i
    
if N > 10**6:
    i = 2
    f = True
    while i <= N**0.5:
        if N%i == 0:
            f = False
            break
        i += 1
    if f:
        ans += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,S = map(int, input().split())
A = [int(a) for a in input().split()]
mod = 998244353

dp = [[0]*(S+1) for _ in range(N+1)]
#dp[i][j]:集合{A[k]|k=0,1,,,i}の部分集合の部分集合のうち、要素の総和がjになるものの個数
dp[0][0] = 1
for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += 2*dp[i][j] #A[i]を使わない場合、集合{A[k]|k=0,1,,,i}の部分集合の数が2倍だけ増える
        dp[i+1][j] %= mod
        if j+A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j] #A[i]を使う場合、総和がjになる部分集合にA[i]を足せばよいので、個数はdp[i][j]だけ増える
            dp[i+1][j+A[i]] %= mod

print(dp[N][S])

Fixed submission:
N,S = map(int, input().split())
A = [int(a) for a in input().split()]
mod = 998244353

dp = [[0]*(S+1) for _ in range(N+1)]
#dp[i][j]:集合{A[k]|k=0,1,,,i}の部分集合の部分集合のうち、要素の総和がjになるものの個数
dp[0][0] = 1
for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += 2*dp[i][j] #A[i]を使わない場合、集合{A[k]|k=0,1,,,i}の部分集合の数が2倍だけ増える
        dp[i+1][j] %= mod
        if j+A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j] #A[i]を使う場合、総和がjになる部分集合にA[i]を足せばよいので、個数はdp[i][j]だけ増える
            dp[i+1][j+A[i]] %= mod

print(dp[N][S])

Buggy python submission (verdict: Time Limit Exceeded):
N,S = map(int, input().split())
A = [int(a) for a in input().split()]
mod = 998244353

A.sort()
num = 0
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    num += A[i]
    for j in range(i+1, 0, -1):
        for k in range(A[i], min(num, S)+1):
            dp[j][k] += dp[j-1][k-A[i]]

ans = 0
for i in range(1, N+1):
    ans += dp[i][S]*pow(2, N-i, mod)
    ans %= mod
print(ans)

Fixed submission:
N,S = map(int, input().split())
A = [int(a) for a in input().split()]
mod = 998244353

dp = [[0]*(S+1) for _ in range(N+1)]
#dp[i][j]:集合{A[k]|k=0,1,,,i}の部分集合の部分集合のうち、要素の総和がjになるものの個数
dp[0][0] = 1
for i in range(N):
    for j in range(S+1):
        dp[i+1][j] += 2*dp[i][j] #A[i]を使わない場合、集合{A[k]|k=0,1,,,i}の部分集合の数が2倍だけ増える
        dp[i+1][j] %= mod
        if j+A[i] <= S:
            dp[i+1][j+A[i]] += dp[i][j] #A[i]を使う場合、総和がjになる部分集合にA[i]を足せばよいので、個数はdp[i][j]だけ増える
            dp[i+1][j+A[i]] %= mod

print(dp[N][S])
Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())

L = [0]*N
j = 1
for i in range(1, M+1):
    while L[j-1] == 1:
        j += 1
    print(j, i+j)
    L[j-1] = 1
    L[i+j-1] = 1

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

a = 1
b = N
for i in range(M, 0, -1):
    if i%2 == M%2:
        print(a, a+i)
        a += 1
    else:
        print(b, b-i)
        b -= 1
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
mod = 2019
L = [0]*mod
n = 0
for i in range(len(S)-1, -1, -1):
    n += (int(S[i])*10**(len(S)-i-1))%mod
    n %= mod
    L[n] += 1

ans = 0
L[0] += 1
for l in L:
    ans += l*(l-1)//2
print(ans)

Fixed submission:
S = input()
mod = 2019
L = [0]*mod
n = 0
for i in range(len(S)-1, -1, -1):
    n += int(S[i])*pow(10, len(S)-i-1, mod)
    n %= mod
    L[n] += 1

ans = 0
L[0] += 1
for l in L:
    ans += l*(l-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H,W,K = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0]*(W) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "1":
            L[i][j] = 1
        
ans = H*W
for i in range(2**(H-1)):
    cnt = 0
    used = [0]*W
    memo = []
    for j in range(H-1):
        if i & (1<<j):
            cnt += 1
            memo.append(j+1)
    memo.append(H)
    num = [0]*(cnt+1)
    for j in range(W):
        idx = 0
        for k in range(H):
            if memo[idx] == k:
                idx += 1
            num[idx] += L[k][j]
        f = False
        for k in range(len(num)):
            if num[k] > K:
                f = True
                break
        if f:
            if j == 0 or used[j-1] == 1:
                cnt = H*W
                break
            used[j-1] = 1
            cnt += 1
            num = [0]*len(num)
            idx = 0
            for k in range(H):
                if memo[idx] == k:
                    idx += 1
                num[idx] += L[k][j]
    ans = min(ans, cnt)
print(ans)

Fixed submission:
H,W,K = map(int, input().split())
S = [input() for _ in range(H)]

L = [[0]*(W) for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == "1":
            L[i][j] = 1
        
ans = H*W
for i in range(2**(H-1)):
    cnt = 0
    used = [0]*W
    memo = []
    for j in range(H-1):
        if i & (1<<j):
            cnt += 1
            memo.append(j+1)
    memo.append(H)
    num = [0]*(cnt+1)
    for j in range(W):
        idx = 0
        for k in range(H):
            if memo[idx] == k:
                idx += 1
            num[idx] += L[k][j]
        f = False
        for k in range(len(num)):
            if num[k] > K:
                f = True
                break
        if f:
            if j == 0 or used[j-1] == 1:
                cnt = H*W
                break
            used[j-1] = 1
            cnt += 1
            num = [0]*len(num)
            idx = 0
            for k in range(H):
                if memo[idx] == k:
                    idx += 1
                num[idx] += L[k][j]
    ans = min(ans, cnt)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
H,W = map(int, input().split())
S = [input() for _ in range(H)]

q = deque()
inf = 10**6
used = [[inf]*W for _ in range(H)]
if S[0][0] == ".":
    used[0][0] = 0
else:
    used[0][0] = 1
q.append((0, 0))

while q:
    temp = q.popleft()
    r = temp[0]
    c = temp[1]
    if r < H-1:
        if S[r+1][c] == "#" and S[r][c] == ".":
            used[r+1][c] = min(used[r+1][c], used[r][c] + 1)
            q.append((r+1, c))
        else:
            used[r+1][c] = min(used[r+1][c], used[r][c])
            q.append((r+1, c))
    if c < W-1:
        if S[r][c+1] == "#" and S[r][c] == ".":
            used[r][c+1] = min(used[r][c+1], used[r][c] + 1)
            q.append((r, c+1))
        else:
            used[r][c+1] = min(used[r][c+1], used[r][c])
            q.append((r, c+1))
    
print(used[-1][-1])

Fixed submission:
H,W = map(int, input().split())
S = [input() for _ in range(H)]

inf = 10**6
L = [[inf]*W for _ in range(H)]
if S[0][0] == ".":
    L[0][0] = 0
else:
    L[0][0] = 1

for i in range(H):
    for j in range(W):
        n1 = inf
        n2 = inf
        if i > 0:
            if S[i-1][j] == "." and S[i][j] == "#":
                n1 = L[i-1][j] + 1
            else:
                n1 = L[i-1][j]
        if j > 0:
            if S[i][j-1] == "." and S[i][j] == "#":
                n2 = L[i][j-1] + 1
            else:
                n2 = L[i][j-1]
        L[i][j] = min(L[i][j], n1, n2)

print(L[-1][-1])
Buggy python submission (verdict: Runtime Error):
import copy
N = int(input())

L = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

ans = []

def f(List):
    if sum(List) == N:
        List.sort(reverse=True)
        s = ""
        for i in range(10):
            s += L[i]*List[i]
        ans.append(s)
    for i in range(9):
        if List[i+1] == 0:
            n = List[i]
            idx = i+1
            break
    for i in range(1, min(n, N-sum(List))+1):
        List2 = copy.copy(List)
        List2[idx] = i
        f(List2)

for i in range(1, N+1):
    List = [0]*10
    List[0] = i
    f(List)

ans.sort()
for a in ans:
    print(a)

Fixed submission:
N = int(input())

L = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]

ans = []
def f(List, n):
    if n == N:
        s = ""
        for l in List:
            s += L[l]
        ans.append(s)
        return None
    for i in range(max(List)+2):
        f(List+[i], n+1)

f([0], 1)        
ans.sort()
for a in ans:
    print(a)
Buggy python submission (verdict: Time Limit Exceeded):
H,N = map(int, input().split())
A = []
B = []
for _ in range(N):
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)

dp = [10**9]*(H+1)
dp[0] = 0
for i in range(N):
    for j in range(H+1):
        if j < A[i]:
            dp[j] = min(dp[j], B[i])
        else:
            dp[j] = min(dp[j], B[i]+dp[j-A[i]])

print(dp[H])

Fixed submission:
from operator import itemgetter
H,N = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

L.sort(key=itemgetter(1))
inf = 10**9
dp = [[inf]*(H+1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    for j in range(H+1):
        if j < L[i][0]:
            dp[i+1][j] = min(dp[i][j], L[i][1])
        else:
            dp[i+1][j] = min(dp[i][j], dp[i+1][j-L[i][0]]+L[i][1])
    for j in range(H, -1, -1):
        if dp[i+1][j] < inf:
            num = dp[i+1][j] + dp[i+1][H-j]
            break
    for j in range(H, -1, -1):
        if dp[i+1][j] > num:
            dp[i+1][j] = num
        else:
            num = dp[i+1][j]

print(dp[N][H])
Buggy python submission (verdict: Time Limit Exceeded):
N,D,A = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

L.sort()
ans = 0
for i in range(N):
    if L[i][1] <= 0:
        continue
    num = L[i][1]//A+min(1, L[i][1]%A)
    ans += num
    j = i+1
    while j < N and L[j][0] <= L[i][0]+2*D:
        L[j][1] -= num*A
        j += 1

print(ans)

Fixed submission:
N,D,A = map(int, input().split())
L = [[int(l) for l in input().split()] for _ in range(N)]

class Bit:
    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

bit = Bit(N)
L.sort()
X = []
for i in range(N):
    X.append(L[i][0])

import bisect
ans = 0
for i in range(N):
    L[i][1] -= bit.sum(N)-bit.sum(i)
    if L[i][1] <= 0:
        continue
    num = L[i][1]//A+min(1, L[i][1]%A)
    ans += num
    j = bisect.bisect_right(X, L[i][0]+2*D)
    if j > i:
        bit.add(j, num*A)
    
print(ans)