Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

z=int(input())

def inv_gcd(a, b):
    a = (a + b) % b
    if a == 0:
        return (b, 0)
    s, t = b, a
    m0, m1 = 0, 1
 
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
 
        tmp = s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    
    if m0 < 0:
        m0 += b // s
    return (s, m0)
 
 
def crt(r, m):
    n = len(r)
    r0, m0 = 0, 1
 
    for i in range(n):
        r1, m1 = (r[i] + m[i]) % m[i], m[i]
 
        if m0 < m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue
        
        g, im = inv_gcd(m0, m1)
 
        u1 = m1 // g
        if (r1 - r0) % g:
            return (0, 0)
        
        x = (r1 - r0) // g % u1 * im % u1
 
        r0 += x * m0
        m0 *= u1
        if (r0 < 0):
            r0 += m0
        
    return (r0, m0)



def divisors(n):
  lower_divisors , upper_divisors = [], []
  i = 1
  while i*i <= n:
    if n % i == 0:
      lower_divisors.append(i)
      if i != n // i:
        upper_divisors.append(n//i)
    i += 1
  return lower_divisors + upper_divisors[::-1]

#print(divisors(2*z))

# for n in range(1,10):
#   # (変数) = (条件がTrueのときの値) if (条件) else (条件がFalseのときの値)
#   ans = n-1 if n%2 else 2*n-1
#   print(ans)

#print(chinese_remainder([2, 3, 2], [3, 5, 7]))

ans = z-1 if z%2 else 2*z-1
for i in divisors(2*z):
  y=2*z//i
  if y == 1:
    continue
  a=[0,-1]
  b=[i,y]
  rem, mod = crt(a, b)
  if rem == mod == 0:
      continue
  ans = min(ans, rem)

print(ans if z-1 else 1)

### FIXED CODE ###

def inv_gcd(a, b):
    a = (a + b) % b
    if a == 0:
        return (b, 0)
    s, t = b, a
    m0, m1 = 0, 1
 
    while t:
        u = s // t
        s -= t * u
        m0 -= m1 * u
 
        tmp = s
        s = t
        t = tmp
        tmp = m0
        m0 = m1
        m1 = tmp
    
    if m0 < 0:
        m0 += b // s
    return (s, m0)
 
 
def crt(r, m):
    n = len(r)
    r0, m0 = 0, 1
 
    for i in range(n):
        r1, m1 = (r[i] + m[i]) % m[i], m[i]
 
        if m0 < m1:
            m0, m1 = m1, m0
            r0, r1 = r1, r0
        
        if m0 % m1 == 0:
            if r0 % m1 != r1:
                return (0, 0)
            continue
        
        g, im = inv_gcd(m0, m1)
 
        u1 = m1 // g
        if (r1 - r0) % g:
            return (0, 0)
        
        x = (r1 - r0) // g % u1 * im % u1
 
        r0 += x * m0
        m0 *= u1
        if (r0 < 0):
            r0 += m0
        
    return (r0, m0)


def divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  divisors.sort()
  return divisors


# print(divisors(z))

z=int(input())


ans = z-1 if z%2 else 2*z-1
for i in divisors(2*z):
  y=2*z//i
  if y == 1:
    continue
  a=[0,-1]
  b=[i,y]
  rem, mod = crt(a, b)
  #print(rem)
  #print(mod)
  if rem == mod == 0:
      continue
  ans = min(ans, rem)

print(ans if z-1 else 1)
### BUGGY CODE ###

import numpy as np
U = 10**5+10
T = np.zeros(U, np.bool)
T[1] = 1
T[2] = 1
T[3::2] = 1
for i in range(3,U,2):
  if i*i>U:
    break
  if T[i]:
    T[i*i::i+i] = 0
A = np.zeros(U, np.bool)
for i in range(U):
  if T[i]==1 and T[(i+1)//2]==1:
     A[i] = 1
A[1] = 0
A[2] = 0
A = A.cumsum()
    
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  print(A[r]-A[l-1])
  

### FIXED CODE ###

import numpy as np
U = 10**5+10
T = np.zeros(U, np.bool)
T[1] = 1
T[2] = 1
T[3::2] = 1
for i in range(3,U,2):
  if i*i>U:
    break
  if T[i]:
    T[i*i::i+i] = 0
A = np.zeros(U, np.bool)
for i in range(3,U,2):
  if T[i]==1 and T[(i+1)//2]==1:
     A[i] = 1
A[1] = 0
A[2] = 0
A = A.cumsum()
    
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  print(A[r]-A[l-1])
### BUGGY CODE ###

n, p = map(int,input().split())
s = str(input())
ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            ans += i+1
    print(ans)
    exit()

tmp = [0] * p
tmp[0] = 1
mod = 0
for i in range(1,n+1):
    mod += (int(s[-i]) * 10**i) % p
    mod %= p
    tmp[mod] += 1

for i in tmp:
    ans += i*(i-1)//2

print(ans)

### FIXED CODE ###

n, p = map(int,input().split())
s = str(input())
ans = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i])%p == 0:
            ans += i+1
    print(ans)
    exit()

tmp = [0] * p
tmp[0] = 1
mod = 0
r = 1
for i in range(1,n+1):
    mod += (int(s[-i]) * r) % p
    mod %= p
    tmp[mod] += 1
    r *= 10
    r %= p

for i in tmp:
    ans += i*(i-1)//2

print(ans)
### BUGGY CODE ###

def main():
    N, K = tuple(int(c) for c in input().split(' '))
    A = [1] + list(int(c) for c in input().split(' '))

    S = 1
    for i in range(1, K+1):
        S *= A[i]
    for i in range(K+1, N+1):
        S2 = S * A[i] // A[i-K]
        if S2 > S:
            print('Yes')
        else:
            print('No')
        S = S2


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, K = tuple(int(c) for c in input().split(' '))
    A = [1] + list(int(c) for c in input().split(' '))

    for i in range(K+1, N+1):
        if A[i] > A[i-K]:
            print('Yes')
        else:
            print('No')

if __name__ == "__main__":
    main()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import math

MOD = 10**9+7  # type: int

def combi_count(n, r):
    return math.factorial(int(n)) // (math.factorial(int(r)) * math.factorial(int(n - r)))

def solve(X: int, Y: int):
    a = (2*Y - X)/3
    b = (2*X - Y)/3
    if ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0):
        ans = 0
    else:
        if (a<0) or (b<0):
            ans = 0
        else:
            ans = combi_count(a+b, min(a, b))
    print(int(ans%MOD))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    solve(X, Y)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math

MOD = 10**9+7  # type: int

def combi_count(n, r):
    x = 1
    y = 1
    for i in range(1, r+1):
        x = x * (n-i) % MOD
        y = y * i % MOD

    # nCr = n!/((n-r)!*r!) = (n!/(n-r)!) / r! 
    #     :=                 (    x    ) / y

    # x / y            % MOD
    # x * y^(-1)       % MOD
    # x * y**(MOD - 2) % MOD (from フェルマー定理)

    return x * pow(y, MOD-2, MOD) % MOD

def solve(X: int, Y: int):
    a = int((2*Y - X)/3)
    b = int((2*X - Y)/3)
    if ( ((2*Y - X)%3 != 0) and ((2*X - Y)%3 != 0) )  or ((a<0) or (b<0)):
        ans = 0
    else:
        ans = combi_count(a+b+1, min(a, b))
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    X, Y = map(int, input().split())
    solve(X, Y)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N):
    if i == 0:
        print(max(A[1:N]))
    elif i == N -1:
        print(max(A[0:N-1]))
    else:
        print(max([max(A[0:i]), max(A[i+1:N])]))
    



### FIXED CODE ###

from sys import stdin
input = stdin.readline

N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A)
first = B[-1]
second = B[-2]

for i in range(N):
    if A[i] == first:
        print(second)
    else:
        print(first)
### BUGGY CODE ###

while True:
        try:
                n = int(raw_input())
                era=[True]*(n)
                for i in xrange(2,n):
                        if(era[i-1]):
                                for j in xrange(i*i-1,n,i):
                                        era[j]=False
                print era[1:n].count(True)
        except EOFError:
                break

### FIXED CODE ###

era = [True]*1000001
for i in xrange(2,1000001):
        if era[i-2]:
                for j in xrange(i*2,1000001,i):
                        era[j-2]=False
while True:
        try:
                n = int(raw_input())
                print era[:n-1].count(True)
        except EOFError:
                break
### BUGGY CODE ###

import numpy as np


def calculate(h, w, arr):
    L = np.zeros([h, w])
    U = np.zeros([h, w])
    D = np.zeros([h, w])
    R = np.zeros([h, w])

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == 1:
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1

            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == 1:
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = input()
    tmp = []
    for qs in q:
        if qs == "#":
            tmp.append(1)
        if qs == ".":
            tmp.append(0)
    arr.append(tmp)

calculate(H, W, arr)


### FIXED CODE ###

def calculate(h, w, arr):
    L = [[0]*w for i in range(h)]
    U = [[0]*w for i in range(h)]
    D = [[0]*w for i in range(h)]
    R = [[0]*w for i in range(h)]

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == 1:
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1

            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == 1:
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = input()
    tmp = []
    for qs in q:
        if qs == "#":
            tmp.append(1)
        if qs == ".":
            tmp.append(0)
    arr.append(tmp)

calculate(H, W, arr)
### BUGGY CODE ###

n, a, b, c = map(int, input().split())
mod = 10 ** 9 + 7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

an = n
bn = n
for i in range(n):
    an *= a
    an *= (a + b)
    an %= mod
    bn *= b
    bn *= (a + b)
    bn %= mod
sum_a = an
sum_b = bn
for i in range(1, n):
    an *= (n + i)
    an *= mod_inv(i, mod)
    an *= b
    an *= mod_inv(a + b, mod)
    an %= mod
    bn *= (n + i)
    bn *= mod_inv(i, mod)
    bn *= a * mod_inv(a + b, mod)
    bn %= mod
    sum_a += an
    sum_a %= mod
    sum_b += bn
    sum_b %= mod
total = (sum_a + sum_b) * 100
q = 1
for i in range(2 * n):
    q *= (a + b)
    q %= mod
q *= (100 - c)
print(total * mod_inv(q, mod) % mod)

### FIXED CODE ###

n, a, b, c = map(int, input().split())
mod = 10 ** 9 + 7

def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]

def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

an = n
bn = n
for i in range(n):
    an *= a
    an *= (a + b)
    an %= mod
    bn *= b
    bn *= (a + b)
    bn %= mod
sum_a = an
sum_b = bn
inv_ab = mod_inv(a + b, mod)
for i in range(1, n):
    an *= (n + i)
    an *= mod_inv(i, mod)
    an *= b
    an *= inv_ab
    an %= mod
    bn *= (n + i)
    bn *= mod_inv(i, mod)
    bn *= a
    bn *= inv_ab
    bn %= mod
    sum_a += an
    sum_b += bn
total = (sum_a + sum_b) * 100
q = 1
for i in range(2 * n):
    q *= (a + b)
    q %= mod
q *= (100 - c)
print(total * mod_inv(q, mod) % mod)
### BUGGY CODE ###

import sys


def main():
    input = sys.stdin.readline

    h, w, k = map(int, input().split())
    s = [input() for _ in range(h)]

    cs = [[0] * (w + 1) for _ in range(h + 1)]
    for i in range(h):
        for j in range(w):
            cs[i +
               1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        cand0 = cand
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline

    h, w, k = map(int, input().split())
    s = [input() for _ in range(h)]

    cs = [[0] * (w + 1) for _ in range(h + 1)]
    for i in range(h):
        for j in range(w):
            cs[i +
               1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        if cand >= ans:
            continue
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1
            if cand >= ans:
                break

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

n = 1
A = []
while True:
    A.append(N//n)
    if N//(n+1) < n+1: break
    n += 1
A.append(n)

L = 2*n
dp = [[0]*L for _ in range(K)]
for l in range(n):
    dp[0][l] = 1

i = 0
for l in reversed(range(n, L)):
    dp[0][l] = A[i] - A[i+1]
    i += 1

for k in range(1, K):
    s = 0
    for l in reversed(range(L)):
        s = (s+dp[k-1][L-l-1]) % mod
        dp[k][l] = s * dp[0][l] % mod

ans = 0
for l in range(L):
    ans = (ans + dp[K-1][l]) % mod

print(ans)

### FIXED CODE ###

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

n = 1
A = []
while True:
    A.append(N//n)
    if N//(n+1) < n+1: break
    n += 1
A.append(n)

L = 2*n
dp = [[0]*L for _ in range(K)]
for l in range(n):
    dp[0][l] = 1

i = 0
for l in reversed(range(n, L)):
    dp[0][l] = A[i] - A[i+1]
    i += 1

for k in range(1, K):
    s = 0
    for l in reversed(range(L)):
        s = (s+dp[k-1][L-l-1]) % mod
        dp[k][l] = s * dp[0][l] % mod

ans = 0
for l in range(L):
    ans = (ans + dp[K-1][l]) % mod

print(ans)
### BUGGY CODE ###

# ABC151 D-Maze Master
import queue
H,W = map(int,input().split())
maze = [input() for _ in range(H)]
dydx = ((0,1),(0,-1),(1,0),(-1,0))

def reach(sy,sx,gy,gx):
    visited = [[0]*W for _ in range(H)]
    q = queue.Queue()
    q.put((sy,sx,0))
    while(not q.empty()):
        y,x,d = q.get()
        if [y,x] == [gy,gx]:
            ans = d
            break
        for dy,dx in dydx:
            if (0<=y+dy<H)&(0<=x+dx<W):
                if maze[y+dy][x+dx] == '#' or visited[y+dy][x+dx] == 1:
                    continue
                visited[y+dy][x+dx] = 1
                q.put((y+dy,x+dx,d+1))
    return ans

d = -1
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '#':
            continue
        for gy in range(H):
            for gx in range(W):
                if maze[gy][gx] == '#' or [sy,sx] == [gy,gx]:
                    continue
                d = max(d,reach(sy,sx,gy,gx))
                
print(d)

### FIXED CODE ###

# ABC151 D-Maze Master
import queue
H,W = map(int,input().split())
maze = [input() for _ in range(H)]
dydx = ((0,1),(0,-1),(1,0),(-1,0))

def reach(sy,sx):
    visited = [[0]*W for _ in range(H)]
    visited[sy][sx] = 1
    q = queue.Queue()
    q.put((sy,sx,0))
    while True:
        y,x,d = q.get()
        for dy,dx in dydx:
            if (0<=y+dy<H)&(0<=x+dx<W):
                if (maze[y+dy][x+dx] == '#') or (visited[y+dy][x+dx] == 1):
                    continue
                visited[y+dy][x+dx] = 1
                q.put((y+dy,x+dx,d+1))
        if q.empty():
            ans = d
            break
    return ans

d = -1
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == '#':
            continue
        d = max(d,reach(sy,sx))
                
print(d)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

def solve():
    N, Q = map(int, input().split())
    graph = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        graph[a].append(b)
        graph[b].append(a)
    ans = [0] * N
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        ans[p] += x
    def dfs(cur, pre):
        for to in graph[cur]:
            if to == pre:
                continue
            ans[to] += ans[cur]
            dfs(to, cur)
    dfs(0, -1)
    print(*ans)
    return

solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

def solve():
    N, Q = map(int, input().split())
    graph = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        graph[a].append(b)
        graph[b].append(a)
    ans = [0] * N
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        ans[p] += x
    def dfs(cur, pre):
        for to in graph[cur]:
            if to == pre:
                continue
            ans[to] += ans[cur]
            dfs(to, cur)
    dfs(0, -1)
    print(*ans)
    return

solve()
### BUGGY CODE ###

import math
n = int(input())

cnt = 0
cnt2 = 0
for i in range(1, n):
    k = n-i
    for j in range(1, int(math.sqrt(k+1))+1):
        if k%j == 0:
            if j == math.sqrt(k):
                cnt2 += 1
            else:
                cnt += 1

print(int(cnt*2)+cnt2)

### FIXED CODE ###

n = int(input())
cnt = 0
for a in range(1,n):
    cnt += (n-1)//a
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
S = [0]*N
for i in range(N):
    x, h = map(int, input().split())
    if h % A == 0:
        h //= A
    else:
        h = h//A + 1
    S[i] = [x, h]

S.sort()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    cnt += S[i][1]
    dmg = S[i][1]
    max_X = S[i][0] + D*2
    for j in range(i+1, N):
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg

print(cnt)


### FIXED CODE ###

from collections import deque
import math

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
S = [0]*N
atack = deque()
for i in range(N):
    x, h = map(int, input().split())
    S[i] = [x, h]

S.sort()
cnt = 0
dmg = 0
for i in range(N):
    while atack:
        if atack[0][0] < S[i][0]:
            x, d = atack.popleft()
            dmg -= d
        else:
            break

    if S[i][1] <= dmg:
        continue
    bomb = math.ceil((S[i][1]-dmg)/A)
    atack.append([S[i][0]+2*D, A*bomb])
    cnt += bomb
    dmg += A*bomb

print(cnt)