Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = input().split()
b = []
if n % 2:
    for i in range(n):
        if i % 2 == 0:
            b.insert(0, a[i])
        else:
            b.append(a[i])
else:
    for i in range(n):
        if i % 2:
            b.insert(0, a[i])
        else:
            b.append(a[i])

print(' '.join(b))


Fixed submission:
n = int(input())
a = input().split()
even = a[::2]
odd =a [1::2]

if n % 2:
    even = even[::-1]
    b = even + odd
else:
    odd = odd[::-1]
    b = odd + even

print(' '.join(b))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a = [int(input()) for i in range(N)]

button = [0]
on = 0
ans = 0

while True:
    now = a[on]-1
    ans += 1
    if now not in button:
        if now == 1:
            break
        else:
            on = now
            button.append(now)
    else:
        ans = -1
        break

print(ans)

Fixed submission:
N = int(input())
a = [int(input()) for i in range(N)]

on, ans, flg = 0, 0, 0

for i in range(N):
    now = a[on]-1
    ans += 1
    if now == 1:
        flg = 1
        break
    else:
        on = now

if flg == 1:
    print(ans)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
MOD = 10 ** 9 + 7

N, K = mii()
A = lmii()

S = []
T = []

for a in A:
    if a < 0:
        T.append(a)
    else:
        S.append(a)

lenS = len(S)
lenT = len(T)

ok = False
if lenS > 0:
    if N == K:
        ok = lenT % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    A.sort(key=lambda x: abs(x))
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    S.sort()
    T.sort(reverse=True)
    if K % 2 == 1:
        ans *= S.pop()
    P = []
    while len(S) >= 2:
        x = S.pop()
        x *= S.pop()
        P.append(x)
    while len(T) >= 2:
        x = T.pop()
        x *= T.pop()
        P.append(x)
    P.sort(reverse=True)
    for i in range(K//2):
        ans *= P[i]
        ans %= MOD

print(ans)

Fixed submission:
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
A = list(map(int, input().split()))

S = []
T = []

for a in A:
    if a < 0:
        T.append(a)
    else:
        S.append(a)

lenS = len(S)
lenT = len(T)

ok = False
if lenS > 0:
    if N == K:
        ok = lenT % 2 == 0
    else:
        ok = True
else:
    ok = K % 2 == 0

ans = 1
if not ok:
    A.sort(key=lambda x: abs(x))
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    S.sort()
    T.sort(reverse=True)
    if K % 2 == 1:
        ans *= S.pop()
    P = []
    while len(S) >= 2:
        x = S.pop()
        x *= S.pop()
        P.append(x)
    while len(T) >= 2:
        x = T.pop()
        x *= T.pop()
        P.append(x)
    P.sort(reverse=True)
    for i in range(K//2):
        ans *= P[i]
        ans %= MOD

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
V = 0
E = 0
for i in range(N+1):
    V += i * (N-i+1)
for i in range(N):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    E += a * (N-b+1)
ans = V - E
print(ans)


Fixed submission:
N = int(input())
V = 0
E = 0
for i in range(N+1):
    V += i * (N-i+1)
for i in range(N-1):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    E += a * (N-b+1)
ans = V - E
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def f(n):
    return n * (n+1) // 2

N = int(input())
ans = 0
for i in range(N):
    i += 1
    ans += i * f(N//i)
print(ans)


Fixed submission:
N = int(input())
table = [0] * (N + 1)
for i in range(1, N + 1):
    for j in range(i, N + 1, i):
        table[j] += 1
ans = 0
for i in range(N):
    i += 1
    ans += i * table[i]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):

from collections import defaultdict

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    return fact[a] * ifact[b] * ifact[a-b]


K = int(input())
S = input().strip()
N = len(S)

# 階乗を前処理
fact = defaultdict(int)
fact[0] = 1
for i in range(1, N+K+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD
# 階乗の逆元を前処理
ifact = defaultdict(int)
ifact[N+K] = pow(fact[N+K], MOD-2, MOD)
for i in reversed(range(1, N+K+1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD

ans = 0
for i in range(K+1):
    now = pow(26, K-i, MOD)
    now *= pow(25, i, MOD)
    now %= MOD
    now *= combination(i+N-1, N-1)
    now %= MOD
    ans += now
    ans %= MOD

print(ans)


Fixed submission:

from collections import defaultdict

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    return fact[a] * ifact[b] * ifact[a-b]


K = int(input())
S = input().strip()
N = len(S)

# 階乗を前処理
fact = defaultdict(int)
fact[0] = 1
for i in range(1, N+K+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD
# 階乗の逆元を前処理
ifact = defaultdict(int)
ifact[N+K] = pow(fact[N+K], MOD-2, MOD)
for i in reversed(range(1, N+K+1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD

ans = 0
for i in range(K+1):
    now = pow(26, K-i, MOD)
    now *= pow(25, i, MOD)
    now %= MOD
    now *= combination(i+N-1, N-1)
    now %= MOD
    ans += now
    ans %= MOD

print(ans)
Buggy python submission (verdict: Runtime Error):

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


N = int(input())
A = list(map(int, input().split()))

D = defaultdict(int)
for a in A:
    D[a] += 1

L = []
for k, v in D.items():
    if v > 1:
        continue
    L.append(k)

if len(L) == 0:
    print(0)
    exit()

L.sort()

ans = set()
for n in L:
    if is_prime(n):
        ans.add(n)
    flg = True
    for s in ans:
        if n % s == 0:
            flg = False
            break
    if flg is False:
        continue
    ans.add(n)

print(len(ans))


Fixed submission:

import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

N = int(input())
A = sorted(map(int, input().split()))

if N == 1:
    print(1)
    exit()

if A[0] == A[1] == 1:
    print(0)
    exit()
if A[0] == 1:
    print(1)
    exit()


S = set()

for a in A:
    i = 2
    while a * i <= 10 ** 6:
        S.add(a * i)
        i += 1

ans = []
for a in A:
    if not a in S:
       ans.append(a)


D = defaultdict(int)
for a in ans:
    D[a] += 1

L = []
for k, v in D.items():
    if v > 1:
        continue
    L.append(k)


print(len(L))
Buggy python submission (verdict: Time Limit Exceeded):

N = int(input())
A = list(map(int, input().split()))

ans = 1
for i in range(N):
    ans *= A[i]

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

Fixed submission:
N = int(input())
A = sorted(map(int, input().split()))
if A[0] == 0:
    print(0)
    exit()

ans = 1
for a in A:
    ans *= a
    if ans > 10 ** 18:
        print(-1)
        exit()

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)
Buggy python submission (verdict: Runtime Error):

def P(n):
    cnt = 0
    tmp = 0
    for i in range(1, n):
        if tmp > n:
            break
        tmp += i
        cnt += 1
    return cnt

N = int(input())

if N == 1:
    print(0)
    exit()

e = defaultdict(int)
for i in range(2, int(N ** 0.5) + 1):
    while N % i == 0:
        e[i] += 1
        N //= i

if len(e) == 0:
    print(1)
    exit()

ans = 0
for k, v in e.items():
    ans += P(v)
print(ans)

Fixed submission:
from collections import defaultdict

N = int(input())

if N == 1:
    print(0)
    exit()

e = defaultdict(int)
for i in range(2, int(N ** 0.5) + 1):
    while N % i == 0:
        e[i] += 1
        N //= i
if N != 1:
    e[N] += 1


if len(e) == 0:
    print(1)
    exit()

ans = 0
for k, v in e.items():
    tmp = 0
    i = 0
    while tmp + i + 1 <= v:
        i += 1
        tmp += i
    ans += i

print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

def get_count(x):
    if x == 2:
        return 1
    s = set()
    i = 1
    while x:
        if x - i in s:
            break
        s.add(i)
        x -= i
        i += 1
    return len(s)



N = int(input())

if N == 1:
    print(0)
    exit()

e = defaultdict(int)
for i in range(2, int(N ** 0.5) + 1):
    while N % i == 0:
        e[i] += 1
        N //= i

if len(e) == 0:
    print(1)
    exit()

ans = 0
for k, v in e.items():
    ans += get_count(v)
print(ans)

Fixed submission:
from collections import defaultdict

N = int(input())

if N == 1:
    print(0)
    exit()

e = defaultdict(int)
for i in range(2, int(N ** 0.5) + 1):
    while N % i == 0:
        e[i] += 1
        N //= i
if N != 1:
    e[N] += 1


if len(e) == 0:
    print(1)
    exit()

ans = 0
for k, v in e.items():
    tmp = 0
    i = 0
    while tmp + i + 1 <= v:
        i += 1
        tmp += i
    ans += i

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import defaultdict
from itertools import permutations

sys.setrecursionlimit(10 ** 7)

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

N, M, X = map(int, input().split())
books = []
for i in range(N):
    books.append(list(map(int, input().split())))

ans = INF
for combination in permutations(range(N), N):
    A = defaultdict(int)
    cost = 0
    for c in combination:
        book = books[c]
        cost += book[0]
        for i in range(1, M + 1):
            A[i] += book[i]
        ok = True
        for i in range(1, M + 1):
            if A[i] < X:
                ok = False
                break
        if ok:
            ans = min(ans, cost)

if ans == INF:
    print(-1)
else:
    print(ans)


Fixed submission:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

N, M, X = map(int, input().split())
books = []
for i in range(N):
    books.append(list(map(int, input().split())))

ans = INF
for s in (range(1 << N)):
    A = defaultdict(int)
    cost = 0
    for i in range(N):
        if s >> i & 1:
            book = books[i]
            cost += book[0]
            for i in range(1, M + 1):
                A[i] += book[i]
    ok = True
    for i in range(1, M + 1):
        if A[i] < X:
            ok = False
            break
    if ok:
        ans = min(ans, cost)

if ans == INF:
    print(-1)
else:
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):

import sys
from collections import defaultdict
from itertools import permutations

sys.setrecursionlimit(10 ** 7)

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

N, M, X = map(int, input().split())
books = []
for i in range(N):
    books.append(list(map(int, input().split())))

ans = INF
for combination in permutations(range(N), N):
    A = defaultdict(int)
    cost = 0
    for c in combination:
        book = books[c]
        cost += book[0]
        for i in range(1, M + 1):
            A[i] += book[i]
        ok = True
        for i in range(1, M + 1):
            if A[i] < X:
                ok = False
                break
        if ok:
            ans = min(ans, cost)

if ans == INF:
    print(-1)
else:
    print(ans)


Fixed submission:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

N, M, X = map(int, input().split())
books = []
for i in range(N):
    books.append(list(map(int, input().split())))

ans = INF
for s in (range(1 << N)):
    A = defaultdict(int)
    cost = 0
    for i in range(N):
        if s >> i & 1:
            book = books[i]
            cost += book[0]
            for i in range(1, M + 1):
                A[i] += book[i]
    ok = True
    for i in range(1, M + 1):
        if A[i] < X:
            ok = False
            break
    if ok:
        ans = min(ans, cost)

if ans == INF:
    print(-1)
else:
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):

N, K = map(int, input().split())
A = list(map(int, input().split()))

route = [0]
now_i = 0
loop_len = 0
for i in range(1, N):
    next_i = A[now_i]-1
    if next_i in route:
        loop_len = i - route.index(next_i)
        break
    route.append(next_i)
    now_i = next_i


base = len(route) - loop_len

if K < len(route):
    print(route[K]+1)
else:
    K -= base
    m = K % loop_len
    idx = route[base:][m]
    print(idx+1)



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

route = [0]
routeset = {0}
now_i = 0
loop_len = 0
for i in range(1, N):
    next_i = A[now_i]-1
    if next_i in routeset:
        loop_len = i - route.index(next_i)
        break
    routeset.add(next_i)
    route.append(next_i)
    now_i = next_i


base = len(route) - loop_len

if K < len(route):
    print(route[K]+1)
else:
    K -= base
    m = K % loop_len
    idx = route[base:][m]
    print(idx+1)
Buggy python submission (verdict: Runtime Error):

N, M, K = map(int, input().split())

ans = 0

for i in range(K+1):
    ans += M ** (i+1) * (M-1) ** (N-i-1)
    ans %= MOD

print(ans)

Fixed submission:

from collections import defaultdict

MOD = 998244353

def combination(a, b):
    if b > a - b:
        return combination(a, a - b)
    return fact[a] * ifact[b] * ifact[a-b]


N, M, K = map(int, input().split())

# 階乗を前処理
fact = defaultdict(int)
fact[0] = 1
for i in range(1, N+1):
    fact[i] = fact[i-1] * i
    fact[i] %= MOD
# 階乗の逆元を前処理
ifact = defaultdict(int)
ifact[N] = pow(fact[N], MOD-2, MOD)
for i in reversed(range(1, N + 1)):
    ifact[i-1] = ifact[i] * i
    ifact[i-1] %= MOD

ans = 0
color = M
for x in reversed(range(N)):
    now = color
    now *= combination(N-1, x)
    now %= MOD
    if x <= K:
        ans += now
        ans %= MOD
    color *= M - 1
    color %= MOD

print(ans)
Buggy python submission (verdict: Runtime Error):

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))


# ----------

N = ii()
A = lmii()

bd = defaultdict(int)
ac = defaultdict(int)
for i in range(N):
    a = b = i + 1
    c = d = A[i]
    bd[b-d] += 1
    ac[a+c] += 1

ans = 0
for k, v in bd.items():
    ans += v * ac[k]

print(ans)


Fixed submission:

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))


# ----------

N = ii()
A = lmii()

bd = defaultdict(int)
ac = defaultdict(int)
for i in range(N):
    a = b = i + 1
    c = d = A[i]
    bd[b-d] += 1
    ac[a+c] += 1

ans = 0
for k, v in bd.items():
    ans += v * ac[k]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

dp = [[0] * (n+1) for _ in range(n+1)]

p = []
for i in range(n):
    p.append((a[i], i))
p.sort(key=lambda x: -x[0])

for i in range(n):
    pi = p[i][1]
    for l in range(i+1):
        r = i - l
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + (pi-l)*a[pi])
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ((n-r-1)-pi)*a[pi])

ans = 0
for i in range(n+1):
    ans = max(ans, dp[n][i])

print(ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

dp = [[0] * (n+1) for _ in range(n+1)]

p = []
for i in range(n):
    p.append((a[i], i))
p.sort(key=lambda x: -x[0])

for i in range(n):
    pi = p[i][1]
    for l in range(i+1):
        r = i - l
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + (pi-l)*a[pi])
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ((n-r-1)-pi)*a[pi])

ans = 0
for i in range(n+1):
    ans = max(ans, dp[n][i])

print(ans)

Buggy python submission (verdict: Runtime Error):

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate
import sys
import bisect
import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

N = ii()
A = lmii()

scoret = []

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        scoret.append((i, j, A[i] * abs(i-j)))

scoret.sort(key=lambda x: -x[2])
done_s = set()
done_t = set()
ans = 0
for s, t, score in scoret:
    if s in done_s or t in done_t:
        continue
    ans += score
    done_s.add(s)
    done_t.add(t)

print(ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

dp = [[0] * (n+1) for _ in range(n+1)]

p = []
for i in range(n):
    p.append((a[i], i))
p.sort(key=lambda x: -x[0])

for i in range(n):
    pi = p[i][1]
    for l in range(i+1):
        r = i - l
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + (pi-l)*a[pi])
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ((n-r-1)-pi)*a[pi])

ans = 0
for i in range(n+1):
    ans = max(ans, dp[n][i])

print(ans)
Buggy python submission (verdict: Runtime Error):

import heapq
from collections import defaultdict, deque
from math import ceil, factorial
from fractions import gcd
import sys
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10**9+7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N, K = mii()

ans = N % K
ans = min(ans, N % abs(N-K))

print(ans)

Fixed submission:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial
from fractions import gcd
import sys
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10**9+7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


N, K = mii()

if K == 0 or N == K:
    print(0)
    exit()

d, m = divmod(N, K)

ans = min(m, abs(m-K))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, P = map(int, input().split())
S = input().strip()
L = len(S)

ans = 0
for i in range(L):
    for j in range(i, L):
        s = S[i: j+1]
        if int(s) % P == 0:
            ans += 1

print(ans)



Fixed submission:
N, P = map(int, input().split())
S = input().strip()[::-1]

if P in [2, 5]:
    ans = 0
    for r in range(N):
        if int(S[r]) % P == 0:
            ans += N - r
    print(ans)
    exit()

d = [0] * (N + 1)
ten = 1
for i in range(N):
    a = int(S[i]) * ten % P
    d[i+1] = (d[i] + a) % P
    ten *= 10
    ten %= P

cnt = [0] * P
ans = 0
for i in range(N + 1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
P = list(map(int, input().split()))

d = {}
for i in range(1, 1001):
    d[i] = (i + 1) * (i / 2) / i

ans = 0
for i in range(N-K+1):
    total = 0
    for j in range(K):
        total += d[P[i+j]]
    ans = max(ans, total)

print(ans)

Fixed submission:
from itertools import accumulate


N, K = map(int, input().split())
P = list(map(int, input().split()))

d = {}
for i in range(1, 1001):
    d[i] = (i + 1) * (i / 2) / i

E = []
for p in P:
    E.append((p+1)/2)

cum = list(accumulate(E))
mx = 0
idx = 0
ans = 0
for i in range(N-K+1):
    if i == 0:
        mx = max(mx, cum[i+K-1])
    else:
        mx = max(mx, cum[i+K-1] - cum[i-1])

print(mx)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
P = list(map(int, input().split()))

d = {}
for i in range(1, 1001):
    d[i] = (i + 1) * (i / 2) / i

ans = 0
for i in range(N-K+1):
    total = 0
    for j in range(K):
        total += d[P[i+j]]
    ans = max(ans, total)

print(ans)

Fixed submission:
from itertools import accumulate


N, K = map(int, input().split())
P = list(map(int, input().split()))

d = {}
for i in range(1, 1001):
    d[i] = (i + 1) * (i / 2) / i

E = []
for p in P:
    E.append((p+1)/2)

cum = list(accumulate(E))
mx = 0
idx = 0
ans = 0
for i in range(N-K+1):
    if i == 0:
        mx = max(mx, cum[i+K-1])
    else:
        mx = max(mx, cum[i+K-1] - cum[i-1])

print(mx)
Buggy python submission (verdict: Time Limit Exceeded):
N, D, A = map(int, input().split())
monsters = []
for i in range(N):
    x, h = map(int, input().split())
    monsters.append((x, h))
monsters.sort()

damege_sum = 0
ans = 0
q = []
for i in range(N):
    x, h = monsters[i]
    while q:
        if q[0][0] < x:
            damege_sum -= q[0][1]
            q.pop(0)
    h -= damege_sum
    if h > 0:
        hit = -(-h // A)
        ans += hit
        damage = hit * A
        damege_sum += damage
        q.append((x + 2 * D, damage))

print(ans)




Fixed submission:
from math import ceil


N, D, A = map(int, input().split())
monsters = []
for i in range(N):
    x, h = map(int, input().split())
    monsters.append((x, h))
monsters.sort()


def problem_a(h):
    if h <= 0:
        return 0
    return ceil(h/A)


cnt_sum = 0
cnt = [0] * N
l = 0
for i in range(N):
    while monsters[l][0] + 2 * D < monsters[i][0]:
        cnt_sum -= cnt[l]
        l += 1
    already = cnt_sum * A
    cnt[i] = problem_a(monsters[i][1] - already)
    cnt_sum += cnt[i]

print(sum(cnt))