Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def ranking(x):
    if(x>=400):
        if(x<600):
            return 8
        elif(x<800):
            return 7
        elif (x < 1000):
            return 6
        elif (x < 1200):
            return 5
        elif (x < 1400):
            return 4
        elif (x < 1600):
            return 3
        elif (x < 1800):
            return 2
        elif (x < 2000):
            return 1
x=input()
print(ranking(x))

Fixed submission:
def ranking(x):
    if(x>=400):
        if(x<600):
            return 8
        elif(x<800):
            return 7
        elif (x < 1000):
            return 6
        elif (x < 1200):
            return 5
        elif (x < 1400):
            return 4
        elif (x < 1600):
            return 3
        elif (x < 1800):
            return 2
        elif (x < 2000):
            return 1
x=int(input())
print(ranking(x))

Buggy python submission (verdict: Runtime Error):
def ranking(x):
    if(x>=400):
        if(x<600):
            return 8
        elif(x<800):
            return 7
        elif (x < 1000):
            return 6
        elif (x < 1200):
            return 5
        elif (x < 1400):
            return 4
        elif (x < 1600):
            return 3
        elif (x < 1800):
            return 2
        elif (x < 2000):
            return 1
x=input()
ranking(x)

Fixed submission:
def ranking(x):
    if(x>=400):
        if(x<600):
            return 8
        elif(x<800):
            return 7
        elif (x < 1000):
            return 6
        elif (x < 1200):
            return 5
        elif (x < 1400):
            return 4
        elif (x < 1600):
            return 3
        elif (x < 1800):
            return 2
        elif (x < 2000):
            return 1
x=int(input())
print(ranking(x))
Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd, sqrt

def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0]*(10**6+1)
    for v in a:
        st = Divisor_Set(v)
        st.remove(1)
        for el in st:
            cnt[el] += 1
    f = True
    for i in range(10**6 + 1):
        if cnt[i] > 1:
            f = False
            break
    if f:
        print("pairwise coprime")
    else:
        all_gcd = a[0]
        for i in range(1, n):
            all_gcd = gcd(all_gcd, a[i])
        if all_gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == "__main__":
    main()

Fixed submission:
from math import gcd, sqrt

def Divisor_Set(n):
    s = set()
    for i in range(1, int(sqrt(n))+2):
        if n%i == 0:
            s.add(i)
            s.add(n//i)
    return s

def main():
    n = int(input())
    a = list(map(int, input().split()))
    f = True
    divset = set()
    for v in a:
        st = Divisor_Set(v)
        st.remove(1)
        for el in st:
            if el in divset:
                f = False
                break
            divset.add(el)
        if not f:
            break
    if f:
        print("pairwise coprime")
    else:
        all_gcd = a[0]
        for i in range(1, n):
            all_gcd = gcd(all_gcd, a[i])
        if all_gcd == 1:
            print("setwise coprime")
        else:
            print("not coprime")

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    k = int(input())
    tmp = 7
    mul = 1
    p = 1
    while p < 10**7 and tmp % k != 0:
        mul *= 10
        tmp += 7 * mul
        mul %= k
        tmp %= k
        p += 1
    if tmp % k == 0:
        print(p)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    k = int(input())
    tmp = 7
    mul = 1
    p = 1
    while p < 10**7 and tmp % k != 0:
        mul *= 10
        tmp += 7 * mul
        mul %= k
        tmp %= k
        p += 1
    if tmp % k == 0:
        print(p)
    else:
        print(-1)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def func(n):
    ans = 0
    while n > 0:
        cnt = 0
        for i in range(65):
            if (n & (1<<i)) != 0:
                cnt += 1
        ans += 1
        n %= cnt
    return ans

def main():
    n = int(input())
    s = input()
    ans = [0]*n
    cnt = 0
    for c in s:
        if c == "1":
            cnt += 1
    ad = cnt + 1
    df = cnt - 1
    start_ad = 0
    start_df = 0
    for i in range(n):
        if ad > 0:
            if s[n-1-i] == "1":
                start_ad += pow(2, i, ad)
                start_ad %= ad
        if df > 0:
            if s[n-1-i] == "1":
                start_df += pow(2, i, df)
                start_df %= df
    for i in range(n):
        if s[i] == "0":
            ans[i] = 1
            tmp = (start_ad + pow(2, n-1-i, ad)) % ad
            ans[i] += func(tmp)
        else:
            if cnt == 1:
                ans[i] = 0
            else:
                ans[i] = 1
                tmp = (start_df - pow(2, n-1-i, df)) % df
                ans[i] += func(tmp)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Fixed submission:
def func(n):
    ans = 0
    while n > 0:
        cnt = 0
        for i in range(33):
            if (n & (1<<i)) != 0:
                cnt += 1
        ans += 1
        n %= cnt
    return ans

def main():
    n = int(input())
    s = input()
    ans = [0]*n
    cnt = 0
    for c in s:
        if c == "1":
            cnt += 1
    ad = cnt + 1
    df = cnt - 1
    start_ad = 0
    start_df = 0
    for i in range(n):
        if ad > 0:
            if s[n-1-i] == "1":
                start_ad += pow(2, i, ad)
                start_ad %= ad
        if df > 0:
            if s[n-1-i] == "1":
                start_df += pow(2, i, df)
                start_df %= df
    for i in range(n):
        if s[i] == "0":
            ans[i] = 1
            tmp = (start_ad + pow(2, n-1-i, ad)) % ad
            ans[i] += func(tmp)
        else:
            if cnt == 1:
                ans[i] = 0
            else:
                ans[i] = 1
                tmp = (start_df - pow(2, n-1-i, df)) % df
                ans[i] += func(tmp)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7

MOD_t_MAX = 5*10**5+10

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def MOD_perm(n, r):
    rtn = 1
    for _ in range(r):
        rtn *= n
        rtn %= MOD
        n -= 1
    return rtn

def MOD_inv(a):
    b = MOD
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u = u % MOD
    if u < 0:
        u += MOD
    return u

def main():
    n, m = map(int, input().split())
    ans = 0
    perm = MOD_perm(m, n)
    MOD_COM_init()
    for i in range(n+1):
        tmp = perm * MOD_COM(n, i) % MOD
        ans += (-1)**i * tmp
        ans %= MOD
        perm *= MOD_inv(m-i)
        perm %= MOD
    print(ans*MOD_perm(m, n)%MOD)

if __name__ == "__main__":
    main()

Fixed submission:
MOD = 10**9 + 7

MOD_t_MAX = 5*10**5+10

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def MOD_perm(n, r):
    rtn = 1
    for _ in range(r):
        rtn *= n
        rtn %= MOD
        n -= 1
    return rtn

def main():
    n, m = map(int, input().split())
    ans = 0
    perm = MOD_perm(m, n)
    MOD_COM_init()
    for i in range(n+1):
        tmp = perm * MOD_COM(n, i) % MOD
        ans += (-1)**i * tmp
        ans %= MOD
        if i < n:
            perm *= inv[m-i]
            perm %= MOD
    print(ans*MOD_perm(m, n)%MOD)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    da = [[None]*n for _ in range(64)]
    for i in range(n):
        da[0][i] = a[i]-1
    for i in range(1, 64):
        for j in range(n):
            da[i][j] = da[i-1][da[i-1][j]]
    ans = 0
    for i in range(64):
        p = k&1
        if p == 1:
            ans = da[i][ans]
        k//= 2
    print(ans+1)

if __name__ == "__main__":
    main()


Fixed submission:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = [True]*n
    cnt = 0
    ans = -1
    x = 0
    while f[x]:
        f[x] = False
        cnt += 1
        x = a[x] - 1
        if cnt == k:
            ans = x+1
            break
    if ans != -1:
        print(ans)
    else:
        k -= cnt
        y = a[x] - 1
        tmp = [x]
        while y != x:
            tmp.append(y)
            y = a[y] - 1
        print(tmp[k%(len(tmp))] + 1)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    n, m = map(int, input().split())
    t = [True]*n
    s = [True]*(n+1)
    x = 1
    for _ in range(m):
        while not s[x]:
            x += 1
        s[x] = False
        for i in range(1, n+1):
            if t[i] and x+i<n+1 and s[x+i]:
                print(x, x+i)
                t[i] = False
                s[x+i] = False
                break

if __name__ == "__main__":
    main()


Fixed submission:
def main():
    n, m = map(int, input().split())
    ans = []
    t = [True]*(n+1)
    l = n//2 - 1
    for i in range(1, n//2):
        if l <= 0:
            break
        if not t[i] or not t[i+l]:
            continue
        ans.append([i, i+l])
        t[i] = False
        t[i+l] = False
        l -= 2
    if n % 2 == 1:
        l = n//2
        for i in range(n//2, n):
            if l <= 0:
                break
            if not t[i] or not t[i+l]:
                continue
            ans.append([i, i+l])
            t[i] = False
            t[i+l] = False
            l -= 2
    else:
        l = n//2 - 2
        for i in range(n//2, n):
            if l <= 0:
                break
            if not t[i] or not t[i+l]:
                continue
            ans.append([i, i+l])
            t[i] = False
            t[i+l] = False
            l -= 2
    for i in range(m):
        print(ans[i][0], ans[i][1])

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)
def solve(G, a, lis, pre, p, ans):
    lis2 = np.copy(lis)
    idx = np.searchsorted(lis2, a[p], side="left")
    lis2[idx] = a[p]
    ans[p] = np.searchsorted(lis2, np.inf, side="left")
    for v in G[p]:
        if v == pre:
            continue
        solve(G, a, lis2, p, v, ans)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    G = [[] for _ in range(n)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        G[u].append(v)
        G[v].append(u)
    lis = np.full(n+1, np.inf)
    ans = [None]*n
    solve(G, a, lis, -1, 0, ans)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Fixed submission:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 7)

def solve(G, a, lis, pre, p, ans):
    target = a[p]
    idx = bisect_left(lis, target)
    frm = lis[idx]
    to = target
    lis[idx] = to
    ans[p] = bisect_left(lis, float("inf"))
    for v in G[p]:
        if v == pre:
            continue
        solve(G, a, lis, p, v, ans)
    lis[idx] = frm

def main():
    n = int(input())
    a = list(map(int, input().split()))
    G = [[] for _ in range(n)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        G[u].append(v)
        G[v].append(u)
    lis = [float("inf")]*(n+1)
    ans = [None]*n
    solve(G, a, lis, -1, 0, ans)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 7)
def cmb(n, r):
    if n <= 0 or n < r:
        return 0
    if n == r or r == 0:
        return 1
    if r == 1:
        return n
    return cmb(n-1,r-1) + cmb(n-1,r)
def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnts = [0]*(2*10**5 + 1)
    for v in a:
        cnts[v] += 1
    buf = 0
    for i in range(2*10**5 + 1):
        if cnts[i] > 0:
            buf += cmb(cnts[i], 2)
    for i in range(n):
        x = a[i]
        if cnts[x] <= 1:
            print(buf)
        else:
            ans = buf
            ans -= cmb(cnts[x], 2)
            print(ans + cmb(cnts[x]-1, 2))

if __name__ == "__main__":
    main()

Fixed submission:
def perm(n, r):
    rtn = 1
    for i in range(r):
        rtn *= n-i
    return rtn

def cmb(n, r):
    return perm(n, r) // perm(r, r)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnts = [0]*(2*10**5 + 1)
    for v in a:
        cnts[v] += 1
    buf = 0
    for i in range(2*10**5 + 1):
        if cnts[i] > 0:
            buf += cmb(cnts[i], 2)
    for i in range(n):
        x = a[i]
        if cnts[x] <= 1:
            print(buf)
        else:
            ans = buf
            ans -= cmb(cnts[x], 2)
            print(ans + cmb(cnts[x]-1, 2))

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
def cmb(n, r):
    if n <= 0 or n < r:
        return 0
    if n == r or r == 0:
        return 1
    if r == 1:
        return n
    return cmb(n-1,r-1) + cmb(n-1,r)
def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnts = [0]*(n+1)
    for v in a:
        cnts[v] += 1
    buf = 0
    for i in range(n+1):
        if cnts[i] > 0:
            buf += cmb(cnts[i], 2)
    for i in range(n):
        x = a[i]
        if cnts[x] <= 1:
            print(buf)
        else:
            ans = buf
            ans -= cmb(cnts[x], 2)
            print(ans + cmb(cnts[x]-1, 2))

if __name__ == "__main__":
    main()

Fixed submission:
def perm(n, r):
    rtn = 1
    for i in range(r):
        rtn *= n-i
    return rtn

def cmb(n, r):
    return perm(n, r) // perm(r, r)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnts = [0]*(2*10**5 + 1)
    for v in a:
        cnts[v] += 1
    buf = 0
    for i in range(2*10**5 + 1):
        if cnts[i] > 0:
            buf += cmb(cnts[i], 2)
    for i in range(n):
        x = a[i]
        if cnts[x] <= 1:
            print(buf)
        else:
            ans = buf
            ans -= cmb(cnts[x], 2)
            print(ans + cmb(cnts[x]-1, 2))

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    h, w, k = map(int, input().split())
    s = [input().rstrip() for _ in range(h)]
    t = [[0]*(w+1) for _ in range(h+1)]
    for i in range(h):
        for j in range(w):
            if s[i][j] == "1":
                t[i+1][j+1] = 1
    for i in range(1, h+1):
        for j in range(1, w+1):
            t[i][j] += t[i-1][j] + t[i][j-1] - t[i-1][j-1]
#    for i in range(h+1):
#        print(t[i])
    ans = 10**9
    for i in range(2**(h-1)):
        a, b = 0, 0
        buf = [0]
        for j in range(h-1):
            if ((1<<j) & i) > 0:
                a += 1
                buf.append(j+1)
        buf.append(h)
        x = 0
        F = True
        for j in range(1, w+1):
            f = False
            for l in range(1, len(buf)):
                if t[buf[l]][j] - t[buf[l-1]][j] - t[buf[l]][x] + t[buf[l-1]][x] > k:
                    f = True
            if f:
                b += 1
                x = j-1
                for l in range(1, len(buf)):
                    if t[buf[l]][j] - t[buf[l-1]][j] - t[buf[l]][j-1] + t[buf[l-1]][j-1] > k:
                        F = False
        if a + b < ans and F:
#            print(a, b, i, x)
            ans = a + b
    print(ans)


if __name__ == "__main__":
    main()

Fixed submission:
def main():
    h, w, k = map(int, input().split())
    s = [input().rstrip() for _ in range(h)]
    t = [[0]*(w+1) for _ in range(h+1)]
    for i in range(h):
        for j in range(w):
            if s[i][j] == "1":
                t[i+1][j+1] = 1
    for i in range(1, h+1):
        for j in range(1, w+1):
            t[i][j] += t[i-1][j] + t[i][j-1] - t[i-1][j-1]
#    for i in range(h+1):
#        print(t[i])
    ans = 10**9
    for i in range(2**(h-1)):
        a, b = 0, 0
        buf = [0]
        for j in range(h-1):
            if ((1<<j) & i) > 0:
                a += 1
                buf.append(j+1)
        buf.append(h)
        x = 0
        F = True
        for j in range(1, w+1):
            f = False
            for l in range(1, len(buf)):
                if t[buf[l]][j] - t[buf[l-1]][j] - t[buf[l]][x] + t[buf[l-1]][x] > k:
                    f = True
            if f:
                b += 1
                x = j-1
                for l in range(1, len(buf)):
                    if t[buf[l]][j] - t[buf[l-1]][j] - t[buf[l]][j-1] + t[buf[l-1]][j-1] > k:
                        F = False
                        break
        if a + b < ans and F:
#            print(a, b, i, x)
            ans = a + b
    print(ans)


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    a_n, b_n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ans = 10**8
    for _ in range(m):
        x, y, c = map(int, input().split())
        x -= 1
        y -= 1
        buf = a[x] + b[x] - c
        if buf < ans:
            ans = buf
    a.sort()
    b.sort()
    if a[0] + b[0] < ans:
        ans = a[0] + b[0]
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
def main():
    a_n, b_n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    ans = 10**8
    for _ in range(m):
        x, y, c = map(int, input().split())
        x -= 1
        y -= 1
        buf = a[x] + b[y] - c
        if buf < ans:
            ans = buf
    a.sort()
    b.sort()
    if a[0] + b[0] < ans:
        ans = a[0] + b[0]
    print(ans)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9 + 7
MOD_t_MAX = 2 * 10**6 + 100

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    r1, c1, r2, c2 = map(int, input().split())
    MOD_COM_init()
    a = MOD_COM(r2+1+c2+1, r2+1) - 1
    b = MOD_COM(r2+1+c1, c1) - 1
    c = MOD_COM(r1+c2+1, r1) - 1
    d = MOD_COM(r1+c1, c1) - 1
    ans = a - b - c + d
    print(ans % MOD)

if __name__ == "__main__":
    main()

Fixed submission:
MOD = 10**9 + 7
MOD_t_MAX = 2 * 10**6 + 10

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def main():
    r1, c1, r2, c2 = map(int, input().split())
    MOD_COM_init()
    a = MOD_COM(r2+1+c2+1, r2+1) - 1
    b = MOD_COM(r2+1+c1, c1) - 1
    c = MOD_COM(r1+c2+1, r1) - 1
    d = MOD_COM(r1+c1, c1) - 1
    ans = a - (b + c) + d
    print(ans % MOD)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    h, n = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    dp = [[float("inf")]*(2*10**4+1) for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        p, a, b = i+1, arr[i][0], arr[i][1]
        for j in range(2*10**4+1):
            if j < a:
                dp[p][j] = dp[p-1][j]
            else:
                if dp[p][j-a] + b < dp[p-1][j]:
                    dp[p][j] = dp[p][j-a] + b
                else:
                    dp[p][j] = dp[p-1][j]
    print(min(dp[-1][h:2*10**4+1]))

if __name__ == "__main__":
    main()


Fixed submission:
def main():
    h, n = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(n)]
    dp = [[float("inf")]*(2*10**4+1) for _ in range(n+1)]
    dp[0][0] = 0
    for i in range(n):
        p, a, b = i+1, arr[i][0], arr[i][1]
        for j in range(2*10**4+1):
            if j < a:
                dp[p][j] = dp[p-1][j]
            else:
                if dp[p][j-a] + b < dp[p-1][j]:
                    dp[p][j] = dp[p][j-a] + b
                else:
                    dp[p][j] = dp[p-1][j]
    print(min(dp[-1][h:2*10**4+1]))

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, dis, dam = map(int, input().split())
    mon = [list(map(int, input().split())) for _ in range(n)]
    mon.sort(key=lambda x: x[0])
    imos = [0]*(n+1)
    dis = 2*dis + 1
    ans = 0
    for i in range(n):
        if 0 < i:
            imos[i] += imos[i-1]
        if imos[i] < mon[i][1]:
            tmp = (mon[i][1] - imos[i] + dam - 1) // dam
            ans += tmp
            tmp *= dam
            imos[i] += tmp
            L, R = i, n
            while L+1 < R:
                P = (L+R)//2
                if mon[P][0] < mon[i][0]+dis:
                    L = P
                else:
                    R = P
            imos[L+1] -= tmp
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
from bisect import bisect_left
def main():
    n, dis, dam = map(int, input().split())
    mon = [list(map(int, input().split())) for _ in range(n)]
    mon.sort(key=lambda x: x[0])
    p = [v[0] for v in mon]
    imos = [0]*(n+1)
    dis = 2*dis + 1
    ans = 0
    for i in range(n):
        if 0 < i:
            imos[i] += imos[i-1]
        if imos[i] < mon[i][1]:
            tmp = (mon[i][1] - imos[i] + dam - 1) // dam
            ans += tmp
            tmp *= dam
            imos[i] += tmp
            idx = bisect_left(p, p[i]+dis)
            imos[idx] -= tmp
    print(ans)

if __name__ == "__main__":
    main()