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

def main():
    from math import gcd
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    mod = 1000000007

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

    lcm = 1
    for i in A:
        lcm = lcm * i // gcd(lcm, i)

    ans = 0
    for i in A:
        ans += lcm // i
        ans %= mod

    print(ans)


main()

### FIXED CODE ###

def main():
    from math import gcd
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline

    mod = 1000000007

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

    lcm = 1
    for i in A:
        lcm = lcm * i // gcd(lcm, i)
    lcm %= mod

    ans = 0
    for i in A:
        ans += lcm * pow(i, mod-2, mod)
        ans %= mod

    print(ans)


main()
### BUGGY CODE ###

R,G,B,N=map(int,input().split())
r,g,b,count=0,0,0,0
while(B*b<=N):
	g=0
	while(G*g<=N-B*b):
		r=(-G*g-B*b+N)/R
		if float(r).is_integer():
			count+=1
		g+=1
	b+=1
print(count)

### FIXED CODE ###

R,G,B,N=map(int,input().split())
r,g,b,count=0,0,0,0
for b in range(N+1):
	for g in range(N+1):
		r=-G*g-B*b+N
		if r<0:break
		if (r%R==0): count+=1
print(count)
### BUGGY CODE ###

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

def gcd(m, n):
    if n == 0:
        return m
    return gcd(n, m % n)

LCM = A[0]
for a in A:
    LCM = LCM * a // gcd(LCM, a)

K = max(A)
for X in range(K // 2, M + 1, K):
    for a in A:
        if (X - a // 2) % a != 0:
            break
    else:
        print((M - X) // LCM + 1)
        exit()
print(0)


### FIXED CODE ###

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

def gcd(m, n):
    if n == 0:
        return m
    return gcd(n, m % n)

LCM = A[0]
for a in A:
    LCM = LCM * a // gcd(LCM, a)

step = max(A)
X = step // 2
while X <= M:
    for a in A:
        if (X - a // 2) % a != 0:
            break
    else:
        cnt = X // LCM + (M - X) // LCM + 1
        print(cnt)
        exit()
    X += step
print(0)
### BUGGY CODE ###

N = int(input())

def g(n):
  return ((n**2)+n)//2

goukei = 0
for i in range(1,N+1):
  goukei += (i*g(N//i))
print(goukei)

### FIXED CODE ###

N = int(input())

def g(n):
  return ((n**2)+n)//2

goukei = 0
half = N//2
for i in range(1,half+1):
  goukei += i*g(N//i)

add = list(range(half+1,N+1))
goukei += sum(add)
print(goukei)
### BUGGY CODE ###

# ABC141 D -Powerful Discount Tickets

import numpy

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

str_A = input().split()
int_A = [int(n) for n in str_A]

for i in range(M):
    m_index = numpy.argmax(int_A)
    int_A[m_index] = max(int_A)//2

print(sum(int_A))

### FIXED CODE ###

# ABC141 D -Powerful Discount Tickets

import heapq
import math

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

A = [-int(n) for n in input().split()]

heapq.heapify(A)


for i in range(M):
    heapq.heappush(A, math.ceil(heapq.heappop(A)/2))

print(-sum(A))
### BUGGY CODE ###

E = lambda x: x if x==1 else (x+1)*(x/2)/x
N, K = map(int, input().split())
Es = [E(pi) for pi in map(int, input().split())]
print(max([sum(Es[i:i+K]) for i in range(N+1-K)]))

### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
ans = [0] + list(accumulate(map(lambda x: (int(x)+1)/2., input().split())))
print(max([y-x for x,y in zip(ans, ans[K:])]))
### BUGGY CODE ###

N, K = map(lambda x: int(x), input().split(" "))
As = list(map(lambda x: int(x), input().split(" ")))

multi = 1
pre_multi = 1

for i in range(len(As)):
    multi *= As[i]
    if i >= K-1:
        multi /= As[i-K]
    if i >= K:
        if multi > pre_multi:
            print("Yes")
        else:
            print("No")

    pre_multi = multi



### FIXED CODE ###

N, K = map(lambda x: int(x), input().split(" "))
As = list(map(lambda x: int(x), input().split(" ")))

for i in range(len(As)):
    if i >= K:
        if As[i] > As[i-K]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

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

l = []
m = [P[0]]
for i in range(N):
    if P[i] <= min(m):
        m.append(P[i])
        continue
    else:
        l.append(i)
print(N - len(l))

### FIXED CODE ###

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

l = []
a = P[0]
for i in range(N):
    if P[i] <= a:
        a = P[i]
        continue
    else:
        l.append(i)
print(N - len(l))
### BUGGY CODE ###

S = input()
n = 0
s = []
patern = 0
for i in range(len(S)):
    s.append(S[i])
while n < len(s)//2+1:
    if s[n] is 'x':
        if s[-n-1] is not 'x':
            s.append('x')
            patern += 1
    else:
        if s[-n-1] is 'x':
            s.insert(n,'x')
            patern += 1
        elif s[-n-1] is not s[n]:
            patern = -1
            break
    n += 1
if patern != -1:
    print(patern)
else:
    print(patern)

### FIXED CODE ###

S = input()
n, m = 0, 1
s = []
patern = 0
for i in range(len(S)):
    s.append(S[i])
while n + m < len(s):
    if s[n] is 'x':
        if s[-m] is not 'x':
            s.append('x')
            patern += 1
    else:
        if s[-m] is 'x':
            n -= 1
            patern += 1
        elif s[-m] is not s[n]:
            patern = -1
            break
    n += 1
    m += 1
if patern != -1:
    print(patern)
else:
    print(patern)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
dp = [0] * max(A)

for i in range(N):
    if dp[A[i]-1] != 0:
        dp[A[i]-1] = 2
        continue
    else:
        for j in range(1, max(A)//A[i]+1):
            dp[A[i]*j-1] += 1

ans = 0
for i in range(N):
    if dp[A[i]-1] == 1:
        ans += 1
print(ans)

### FIXED CODE ###

from numba import njit

N = int(input())
A = list(map(int, input().split()))
maxA = max(A)
dp = [0] * maxA

for i in range(N):
    if dp[A[i]-1] != 0:
        dp[A[i]-1] = 2
        continue
    else:
        for j in range(1, maxA//A[i]+1):
            dp[A[i]*j-1] += 1

ans = 0
for i in range(N):
    if dp[A[i]-1] == 1:
        ans += 1

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

import sys
import math
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

II = input_int

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の累積和 s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

subs = [int(S[N - i:]) if S[N - i:] else 0 for i in range(N + 1)]
counter = dict()
for i in range(2019):
    counter[i] = 0

for num in subs:
    counter[num % 2019] += 1

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

ans = 0
for r in counter.values():
    if r >= 2:
        ans += combinations_count(r, 2)
print(ans)

### FIXED CODE ###

S = list(input())
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        sub += int(S[N - i]) * k
        k *= 10
        k %= 2019
    rest = sub % 2019
    counter[rest] += 1

ans = 0
for r in counter:
    ans += r * (r - 1) // 2
print(ans)
### BUGGY CODE ###

from itertools import product, permutations, combinations
import math
N, K = map(int, input().split())
P = list(map(int, input().split()))

ans = math.inf
for pt in combinations(P, K):
    ans = min(ans, sum(pt))

print(ans)
exit()


### FIXED CODE ###

from itertools import product, permutations, combinations
import math
N, K = map(int, input().split())
P = list(sorted((list(map(int, input().split())))))

print(sum([P[i] for i in range(K)]))
exit()
### BUGGY CODE ###

import math
N = int(input())
n = math.floor(math.sqrt(N))
i=0
while True:
  if N%(n+i) == 0:
    print(len(str((n+i))))
    exit()
  else: i+=1

### FIXED CODE ###

import math
N = int(input())
n = math.floor(math.sqrt(N))
for i in range(n):
  if N%(n-i) == 0:
    print(len(str(N//(n-i))))
    exit()
### BUGGY CODE ###

n = int(input())
boss_num = input()

for i in range(1, n+1):
	print (boss_num.count(str(i)))

### FIXED CODE ###

n = int(input())
l = [0]*n
boss_num = list(map(int, input().split()))

for num in boss_num:
	l[num-1] += 1	
for m in l: print(m)
### BUGGY CODE ###



def p(k,w,maxP):
    count = 1
    tmpList = []
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
        else:
            count += 1
            tmpList = []
            tmpList.append(x)
    
    if count > k :
        result = False
    else:
        result = True

    return result


def pout(k,w,maxP):
    tmpList = []
    mP = 0
    for x in w:
        if sum(tmpList)+x <= maxP:
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
        else:
            tmpList = []
            tmpList.append(x)
            mP = max(sum(tmpList),mP)
    

    return mP


n,k = map(int,input().split())


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)+1
rangeMin = 1

while _:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == False and p(k,w,rangeMid+1) == False:
        rangeMin = rangeMid
    elif p(k,w,rangeMid) == True and p(k,w,rangeMid+1) == True:
        rangeMax = rangeMid
    else:
        break

print(pout(k,w,rangeMid+1))

### FIXED CODE ###



def p(k,w,maxP):
    count = 1
    tmpWeight = 0
    for x in w:
        if tmpWeight+x <= maxP:
            tmpWeight += x
        else:
            count += 1
            if count > k :
                return False
            tmpWeight = x
    

    return True




n,k = map(int,input().split())


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)
### BUGGY CODE ###

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

ans = 1
t = 1e18
for i in range(n//2):
    ans *= a[i]
    ans *= a[i+n//2]

if n % 2 == 1:
    ans *= a[n-1]

if ans <= t:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

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

ans = 1
t = 1e18
if 0 in a:
    print(0)
    exit(0)

for i in range(n):
    ans *= a[i]
    if ans > t:
        print(-1)
        exit(0)

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

from collections import Counter

def verify_anagrams(first_word, second_word):
  def get_counter(s):
    return Counter(s.upper().replace(' ', ''))
 
  global ana
  if get_counter(first_word) == get_counter(second_word):
    ana = ana + 1

ana = 0
N = int(input())
S = []
for _ in range(N):
  S.append(str(input()))

for i in range(N):
  for j in range(N):
    verify_anagrams(S[i],S[j])

Ans = int((ana - N)/2)
print(Ans)

### FIXED CODE ###

import sys
 
Ans = 0
N = int(input())
S = []
T = []
U = []
for _ in range(N):
  S.append(str(input()))
T = ['a'] * N  
U = ['a'] * N
 
for i in range(N):
  U[i] = ''.join(sorted(S[i]))
 
T = sorted(U)
 
j = 0
while j < N:
  for k in range(1,N):
    if j + k == N - 1:
      if T[j] != T[j + k]:
        Ans = Ans + (k-1) * k / 2
      else:
        Ans = Ans + (k+1) * k / 2
        
      print(int(Ans))
      sys.exit()
      
    if T[j] != T[j + k]:
      Ans = Ans + (k-1) * k / 2
      a = k
      break
  
  j = j + a
  
print(int(Ans))
### BUGGY CODE ###

import math
A,B,N=map(int, input().split())
NUM=0
for x in range(1,N+1):
    TGT=math.floor(A*x/B)-A*math.floor(x/B)
    if TGT>NUM:
        NUM=TGT
print(NUM)

### FIXED CODE ###

A,B,N = (map(int , input().split()))
min(B-1,N)
x = min(B-1,N)
print(((A*x)//B - A * (x//B)))
### BUGGY CODE ###

N, K = map(int, input().split())
mod = 998244353
move = []

for _ in range(K):
  L, R = map(int, input().split())
  move.append((L, R))

dp = [0]*(2*N+1)
dp[0] = 1

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

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
mod = 998244353
move = []

for _ in range(K):
  L, R = map(int, input().split())
  move.append((L, R))

S = [0]*K
dp = [0]*(2*N)
dp[N] = 1

for i in range(N+1, 2*N):
  for k, (l, r) in enumerate(move):
    S[k] -= dp[i-r-1]
    S[k] += dp[i-l]
    dp[i] += S[k]
  dp[i] %= mod

print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Jan 19 12:14:33 2019
DP_F
@author: maezawa
"""

s = input()
t = input()

ls = len(s)
lt = len(t)

dp = [['']*(lt+1) for _ in range(ls+1)]

for i in range(1, ls+1):
    for j in range(1, lt+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+s[i-1]
        else:
            dp[i][j] = max(dp[i][j],dp[i-1][j], dp[i][j-1], key=len)
        #print((i,j), dp[i][j])

print(dp[-1][-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 09:02:00 2019
DPF3
@author: maezawa
"""

s = input()
t = input()

ns = len(s)
nt = len(t)

dp = [[0 for _ in range(nt+1)] for _ in range(ns+1)]

for si in range(ns):
    for ti in range(nt):
        if s[si] == t[ti]:
            dp[si+1][ti+1] = max(dp[si][ti]+1, dp[si+1][ti], dp[si][ti+1])
        else:
            dp[si+1][ti+1] = max(dp[si+1][ti], dp[si][ti+1])

ans = ''
si = ns
ti = nt
while si > 0 and ti > 0:
    if dp[si][ti] == dp[si-1][ti]: 
        si -= 1
    elif dp[si][ti] == dp[si][ti-1]:
        ti -= 1
    else:
        ans = s[si-1] + ans
        si -= 1
        ti -= 1

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

import numpy as np
import math

def binsearch(a, start, end):
    low = start
    high = end

    mindiff = 2**63
    minpos = 0
    minleftsum = 0
    minrightsum = 0
    premid = -2
    mid = -1

    # print('--start--')
    while low <= high:
        premid = mid
        mid = (low + high) // 2
        leftsum = a[start:mid].sum()
        rightsum = a[mid:end].sum()
        diff = np.abs(leftsum - rightsum)
        if diff < mindiff:
            mindiff = diff
            minpos = mid
            minleftsum = leftsum
            minrightsum = rightsum

        # print(low, high, mid, leftsum, rightsum, diff, minpos)
        if leftsum < rightsum:
            low = mid + 1
        elif leftsum > rightsum:
            high = mid - 1
        else:
            return mid, leftsum, rightsum

    return minpos, minleftsum, minrightsum

def calcfinaldiff(p, q, r, s):
    return max((p, q, r, s)) - min((p, q, r, s))

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

mid0 = binsearch(A, 0, N)[0]
mid1, p, q = binsearch(A, 0, mid0)
mid2, r, s = binsearch(A, mid0, N)

diff = calcfinaldiff(p, q, r, s)

for mid in range(1, N - 1):
    mid1, p, q = binsearch(A, 0, mid)
    mid2, r, s = binsearch(A, mid, N)
    tmpdiff = calcfinaldiff(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)


### FIXED CODE ###

import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    tmp = csA[j+1]
    p = tmp - csA[i]
    q = csA[k+1] - tmp
    return p, q, abs(p - q)

N = int(input())
# A = np.array(list(map(int, input().split())))
# csA = np.cumsum(A)

csA = [0] * (N+1)
for i, v in enumerate(input().split()):
    csA[i+1] = csA[i] + int(v)

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

csAN = csA[N]
for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT
    csAmid1 = csA[mid1+1]

    # mid0 search
    for i in range(mid0, mid1):
        # tmpp, tmpq, tmpdiff0 = getsumanddiff(0, i, mid1)
        tmpp = csA[i+1]
        tmpq = csAmid1 - tmpp
        tmpdiff0 = abs(tmpp - tmpq)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        # tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        csAi = csA[i+1]
        tmpr = csAi - csAmid1
        tmps = csAN - csAi
        tmpdiff2 = abs(tmpr - tmps)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = max(p, q, r, s) - min(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)
### BUGGY CODE ###

from sys import stdin
import sys
sys.setrecursionlimit(10**6)
def S(): return stdin.readline().rstrip()
a = S()
def f(t,a,l):
    if t == a:
        return True
    else:
        for i in l:
            if t+i in a[:len(t+i)]:
                if f(t+i,a,l):
                    return True
        return False

strl = ['dream','dreamer','erase','eraser']
if f('',a,strl):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

from sys import stdin
def S(): return stdin.readline().rstrip()

a = S()
strl = ['dream','dreamer','erase','eraser']
t = ''
for i in range(len(a)-1,-1,-1):
    if 7<len(t):
        print('NO')
        exit()
    else:
        t = a[i]+t
        if t in strl:
            t = ''

print('YES')
### BUGGY CODE ###

h, w= map(int, input().split())
A = [list(map(int, input().split())) for _ in range(h)]
B = [list(map(int, input().split())) for _ in range(h)]

C = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j]-B[i][j])

D = 80*160
dp = [[[0]*D for i in range(w)] for j in range(h)]
dp[0][0][C[0][0]] = 1
for i in range(h):
    for j in range(w):
        if i+1< h:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i+1][j][k+C[i+1][j]] = 1
                    dp[i+1][j][abs(k-C[i+1][j])] = 1
        if j+1<w:
            for k in range(D):
                if dp[i][j][k] != 0:
                    dp[i][j+1][k+C[i][j+1]] = 1
                    dp[i][j+1][abs(k-C[i][j+1])] = 1

for i in range(D):
    if dp[-1][-1][i] != 0:
        print(i)
        exit()

### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
A = [0]*h
B = [0]*h
for _ in range(h):
  A[_] = list(map(int, input().split()))
  
for _ in range(h):
  B[_] = list(map(int, input().split()))

C = [[0]*w for _ in range(h)]
for i in range(h):
  for j in range(w):
    C[i][j] = abs(A[i][j]-B[i][j])
    
dp = [[0]*w for _ in range(h)]
D = 80 * (h + w)
L = 2*D + 1
dp[0][0] = np.zeros(L, np.bool)
dp[0][0][D+C[0][0]] = 1
for i in range(h):
  for j in range(w):
    if i == 0 and j == 0:
      continue
    x = np.zeros(L, np.bool)
    if i != 0:
      x[C[i][j]:] |= dp[i-1][j][:L-C[i][j]]
      x[:L-C[i][j]] |= dp[i-1][j][C[i][j]:]
    if j != 0:
      x[C[i][j]:] |= dp[i][j-1][:L-C[i][j]]
      x[:L-C[i][j]] |= dp[i][j-1][C[i][j]:]
    dp[i][j] = x
    
temp = np.where(dp[-1][-1]>0)[0]-D
temp = np.abs(temp)
print(np.min(temp))
### BUGGY CODE ###

#/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())

adj = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = (a - 1, b - 1)
    adj[a].append(b)
    adj[b].append(a)
    
values = [0 for _ in range(N)]
    
for _ in range(Q):
    p, x = map(int, input().split())
    values[p - 1] += x

def dfs(node, parent):
    for child in adj[node]:
        if child == parent: continue
        values[child] += values[node]
        dfs(child, node)

dfs(0, -1)

print(*values, sep=" ")
    

### FIXED CODE ###

#/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

def input():
    return sys.stdin.readline()

N, Q = map(int, input().split())

adj = [[] for _ in range(N)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    a, b = (a - 1, b - 1)
    adj[a].append(b)
    adj[b].append(a)
    
values = [0 for _ in range(N)]
    
for _ in range(Q):
    p, x = map(int, input().split())
    values[p - 1] += x

def dfs(node, parent):
    for child in adj[node]:
        if child == parent: continue
        values[child] += values[node]
        dfs(child, node)

dfs(0, -1)

print(" ".join(map(str, values)))
### BUGGY CODE ###

import math,bisect
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n,d,a = map(int,readline().split())
lst1 = [list(map(int,readline().split())) for i in range(n)]
lst1.sort()

#####segfunc######
def segfunc(x,y):
    return x+y

def init(init_val): #渡されたリストでsegを初期化
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x): #segの要素kをxに変更(セグ木全体の更新)
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q): #区間[p,q)での、segfuncに準じた値を返す
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
"""
最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
　　和のセグ木 → 0
　　積のセグ木 → 1
　　gcdのセグ木 → 0　(gcdを更新しない値は0)
"""
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num


#process
x = []
for i in lst1:
    x.append(i[0])


ans = 0

for i in range(n):
    k = bisect.bisect_left(x,lst1[i][0]-2*d) #手前側にあるダメージ量を確認

    r = query(k,i) #kからiまでの合計ダメージを取得

    if lst1[i][1] > r:
        if (lst1[i][1]-r)/a%1==0:
            need = (lst1[i][1]-r)//a
        else:
            need = (lst1[i][1]-r)//a+1
        ans += need
        update(i,need*a)

print(ans)


### FIXED CODE ###

import math,bisect
n,d,a = map(int,input().split())
lst1 = [list(map(int,input().split())) for i in range(n)]
lst1.sort()

#解法2 - imos法
"""
単純に座標に対してimos法を行うと、座標の制約は10**9なので間に合わない。
process1
そこで、各モンスターに対して、そのモンスターを左端で攻撃を行った際、右側の巻き込めるモンスターのインデックスを
保存するリストを作る。
process2
これにより、imosのテーブルはn+1個で答えを求めることができる。
また、imosの累積和は順次求めていく感じになる。
"""
x = []
for i in lst1:
    x.append(i[0])

#process1
index = 0
reach = []
for i in range(n):
    index = bisect.bisect_right(x,lst1[i][0]+2*d)
    reach.append(index)

#process2
ans = 0
imos = [0]*(n+1) #その座標に効いている魔法の回数(ダメージ量ではない)

for i in range(n):
    if imos[i]*a < lst1[i][1]: #ダメージが足りないなら
        need = math.ceil((lst1[i][1]-imos[i]*a)/a)
        imos[i] += need
        imos[reach[i]] -= need #届かなくなったとこでマイナス
        ans += need
    imos[i+1] += imos[i] #累積和を逐一とる

print(ans)