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

n,w=map(int,input().split())
W=[]
V=[]

for i in range(n):
	a,b=map(int,input().split())
	W.append(a)
	V.append(b)

def knap(n,w):
	dp=[[0]*(w+1) for i in range(n+1)]
	for i in range(n):
		for j in range(w+1):
			if j<W[i-1]:
				dp[i+1][j]=dp[i][j]
			else:
				dp[i+1][j]=max(dp[i][j],dp[i][j-W[i-1]]+V[i-1])
	return dp[n][w]

print(knap(n,w))


### FIXED CODE ###

n,w=map(int,input().split())
W=[]
V=[]

for i in range(n):
	a,b=map(int,input().split())
	W.append(a)
	V.append(b)

def knap(n,w):
	dp=[[0]*(w+1) for i in range(n+1)]
	for i in range(n):
		for j in range(w+1):
			if j<W[i-1]:
				dp[i+1][j]=dp[i][j]
			else:
				dp[i+1][j]=max(dp[i][j],dp[i][j-W[i-1]]+V[i-1])
	return dp[n][w]

print(knap(n,w))
### BUGGY CODE ###

import bisect

N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""
AB.sort(key=lambda x: (-x[0], x[1]))

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append((a, b))
a0.sort()

nab.sort(key=lambda x: ((x[1] + 1) / x[0]))

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

dp = [0] + [float('inf')] * 29
for index, (a, b) in enumerate(nab):
    # print(a, b)
    ndp = [0] + [float('inf')] * 29
    for count in range(1, 29):
        ndp[count] = min(dp[count],
                                   dp[count - 1] + 1 + (dp[count - 1] + 1) * a + b)
    dp = ndp

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)


### FIXED CODE ###

import bisect

N, T = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(N)]

"""
a_x = 1 and b_x is t_i = 2*(t_i +2) 
n 店舗回るのに 2^nはかかる
30店舗以上は回れない
"""

a0 = []
nab = []
for a, b in AB:
    if a == 0:
        a0.append(b)
    else:
        nab.append(((b + 1) / a, a, b))
a0.sort()

nab.sort()

a0sum = []  # key: n of visit, value : cost
_sum = 0
for b in a0:
    _sum += 1 + b
    a0sum.append(_sum)

INF = 1 << 32
dp = [0] + [INF] * 29
for index, (_, a, b) in enumerate(nab):
    # print(a, b)
    ndp = [0] + [INF] * 29
    for count in range(1, 29):
        ndp[count] = min(dp[count],
                         dp[count - 1] + 1 + (dp[count - 1] + 1) * a + b)
    dp = ndp

ans = 0
# print(a0sum)
# print(nab)
# print(dp)
for count, t in enumerate(dp):
    if t > T:
        continue
    v = bisect.bisect_right(a0sum, T - t)
    ans = max(ans, v + count)
print(ans)
### BUGGY CODE ###

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

a = []
for _ in range(M):
    a.append(int(input()))

val = [0,1]
for i in range(1, N + 1):
    ans = (val[0] + val[1]) % (10**9 +7)
    val[0] = val[1]
    val[1] = ans
    if len(a) > 0:
        if i == a[0]:
            val[1] = 0
            a.pop(0)

print(ans)

### FIXED CODE ###

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

a = []
for _ in range(M):
    a.append(int(input()))

val = [0,1]
for i in range(1, N + 1):
    ans = val[-2] + val[-1]
    val.append(ans)
    if len(a) > 0:
        if i == a[0]:
            val[-1] = 0
            a.pop(0)

print(ans % (10**9 +7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
MOD = 10**9 + 7


def main():
    S = input().rstrip()
    DP = [0] * 13
    n = len(S)
    if S[-1] == '?':
        for i in range(10):
            DP[i] = 1
    else:
        DP[int(S[-1])] = 1

    for i in range(1, n):
        preDP = DP
        DP = [0] * 13
        if S[-i-1] == '?':
            for x in range(10):
                nx = x * 10 ** i
                for k in range(13):
                    t = (nx + k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(S[-i-1]) * 10 ** i
            for k in range(13):
                t = (y+k) % 13
                DP[t] = preDP[k] % MOD
    ans = DP[5]
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
MOD = 10**9 + 7


def main():
    S = input().rstrip()
    DP = [0] * 13
    n = len(S)
    DP[0] = 1

    for i in range(0, n):
        preDP = DP
        DP = [0] * 13
        if S[i] == '?':
            for k in range(13):
                for x in range(10):
                    t = (x + 10*k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(S[i])
            for k in range(13):
                t = (y+10*k) % 13
                DP[t] += preDP[k]
                DP[t] %= MOD

    ans = DP[5]
    print(ans)


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

h,w,m=map(int,input().split())

max_h=[0 for i in range(h+1)]
max_w=[0 for i in range(w+1)]
grid=[[0 for i in range(w)] for j in range(h)]
pro=[list(map(int,input().split())) for i in range(m)]
pro.sort()
for i in range(m):
    h=pro[i][0]
    w=pro[i][1]
    max_h[h]+=1
    max_w[w]+=1
    grid[h-1][w-1]=1
h_max=[i for i, x in enumerate(max_h) if x == max(max_h)]
w_max=[i for i, x in enumerate(max_w) if x == max(max_w)]

ans=0
for i in h_max:
    for j in w_max:
        cnt=0
        for k in range(h):
            if grid[k][j-1]==1:
                cnt+=1
        
        cnt += grid[i-1].count(1)
        if grid[i-1][j-1]==1:
            cnt -= 1
        
        if cnt > ans:
            ans=cnt
print(ans)

### FIXED CODE ###

H, W, M = map(int, input().split())
row=[0]*H #x座標を入れるっちゅうかカウント
col=[0]*W #y座標を入れる
 
mat=[] #座標を入れる
 
for i in range(M):
    h, w = map(int, input().split())
    row[h-1]+=1
    col[w-1]+=1
    mat.append((h-1,w-1))
r=max(row)
c=max(col)
 
rr=[1 if row[i]==r else 0 for i in range(H)] #maxな列のインデックス
cc=[1 if col[i]==c else 0 for i in range(W)] #maxな行のインデックス
 
x=0 #maxな列と行の交差点にある爆弾の個数をカウント
for k in mat:
    if rr[k[0]]==1 and cc[k[1]]==1:
        x+=1
        
if sum(rr)*sum(cc)==x: #行と列の全ての交差点に爆弾があれば-1する
    print(r+c-1)
else:
    print(r+c)
### BUGGY CODE ###

r1, c1, r2, c2 = map(int, input().split())

MOD=10**9+7

def comb(n, r): 
    if r<0 or r>n: 
        return 0
    r=min(r, n-r)
    res=1
    for i in range(r): 
        res=res*(n-i)%MOD*pow(i+1, MOD-2, MOD)%MOD
    return res

ans = comb(r2+c2+2, r2+1)-1
ans -= comb(r2+1+c1, c1)-1
ans -= comb(r1+c2+1, r1)-1
ans += comb(r1+c1, r1)-1

print(ans%MOD)

### FIXED CODE ###

def comb(n, r):
    if r<0 or r>n:
        return 0
    r=min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%MOD

MOD=10**9+7
MAXN=2000000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

for i in range(2, MAXN+1):
    g1.append((g1[-1]*i)%MOD)
    inverse.append(-inverse[MOD%i]*(MOD//i)%MOD)
    g2.append((g2[-1]*inverse[-1])%MOD)

r1, c1, r2, c2=map(int, input().split())
s1=comb(r2+c2+2, r2+1)-1
s2=comb(r1+c2+1, r1)-1
s3=comb(r2+c1+1, r2+1)-1
s4=comb(r1+c1, r1)-1
print((s1-s2-s3+s4)%MOD)
### BUGGY CODE ###

n = int(input())
nums = [int(input()) for _ in range(n)]
p, q = nums.index(1), nums.index(n)
a, b = 1, 1
keep = []

for i in range(2, n+1):
    if  p < nums.index(i):
        a += 1
    else:
        keep.append(a)
        a = 1
    p = nums.index(i)
keep.append(a)
for j in range(n, 0, -1):
    if  q > nums.index(j):
        b += 1
    else:
        keep.append(b)
        b = 1
    q = nums.index(j)
keep.append(b)
print(n - max(keep))

### FIXED CODE ###

n = int(input())
nums = [int(input()) for _ in range(n)]
mem = [0] * (n + 1)
a, b = 1, 1
s = 0
for i in range(n):
    mem[nums[i]] += i

p, q = mem[1], mem[n]

for i in range(2, n+1):
    if  p < mem[i]:
        a += 1
    else:
        s = max(s, a)
        a = 1
    p = mem[i]
s = max(s, a)
for j in range(n, 0, -1):
    if  q > mem[j]:
        b += 1
    else:
        s = max(s, b)
        b = 1
    q = mem[j]
s = max(s, b)
print(n - s)
### BUGGY CODE ###

from collections import deque
import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
# dy = [1,-1,0,0]
# dx = [0,0,1,-1]
que = deque([(i, j) for i in range(H) for j in range(W) if field[i][j]])

count = 0
while True:
    count += 1
    nque = deque()
    while que:
        h,w = que.popleft()
        if w >0 and not field[h][w-1]:
            field[h][w-1] = True
            nque.append([h,w-1])
        if w <W-1 and not field[h][w+1]:
            field[h][w+1] = True
            nque.append([h,w+1])
        if h >0 and not field[h-1][w]:
            field[h-1][w] = True
            nque.append([h-1,w])
        if h < H-1 and not field[h+1][w]:
            field[h+1][w] = True
            nque.append([h+1,w])
        # for i in range(4):
        #     nh = h + dy[i]
        #     nw = w + dx[i]
        #     if (0<=nh<H) and (0<=nw<W):
        #         if field[nh][nw] == False:
        #             field[nh][nw] = True
        #             nqueue.append((nh,nw))
    if nque:
        que = copy.copy(nque)
    else:
        break
print(count-1)

### FIXED CODE ###

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

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

s = input()
q = int(input())
for i in range(q):
    inp = list(input().split())
    if len(inp) == 1:
        s = s[::-1]
        continue
    t, f, c = inp[0], int(inp[1]), inp[2]
    if f == 1:
        s = c + s
    else:
        s = s + c
print(s)


### FIXED CODE ###

s = input()
q = int(input())
reverse = False
front = []
back = []
for i in range(q):
    inp = list(input().split())
    if len(inp) == 1:
        if reverse:
            reverse = False
        else:
            reverse = True
        continue
    t, f, c = inp[0], int(inp[1]), inp[2]
    if not reverse:
        if f == 1:
            front.append(c)
        else:
            back.append(c)
    else:
        if f == 2:
            front.append(c)
        else:
            back.append(c)
s = "".join(front[::-1]) + s + "".join(back)
if reverse:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

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

class Node:
    def __init__(self, data): #コンストラクタ
        self.data = data #ノードがもつ数値
        self.left = None #左エッジ
        self.right = None #右エッジ


class BST:
    def __init__(self, number_list): #コンストラクタ
        self.root = None #ルートノード初期化
        for node in number_list: #数値を持つ配列から二分木を生成
            self.insert(node) #挿入メソッドを使ってノードを挿入する
    #挿入
    def insert(self, data):
        n = self.root
        if n == None:
            self.root = Node(data)
            return
        else:
            while True:
                entry = n.data
                if data < entry:
                    if n.left is None:
                        n.left = Node(data)
                        return
                    n = n.left
                elif data > entry:
                    if n.right is None:
                        n.right = Node(data)
                        return
                    n = n.right
                else:
                    n.data = data
                    return
    def count(self, ans):
        n = self.root
        while True:
        		if n != None:
          			ans += 1
          			n = n.left
        return ans

tree = BST(p)
ans = tree.count(0)

print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
list_a=[]
min = p[0]
for i in p:
  if min >= i:
    min = i
    ans += 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))
mem = [[-1 for _ in range(N)] for _ in range(N)]

dp = [0] * N
dp[1] = abs(H[1]-H[0])


for i in range(2, N):
    l = []
    for k in range(1, 1+K):
        if i-k >= 0:
            if mem[i-k][i] != -1:
                d = mem[i-k][i]
            else:
                d = abs(H[i - k] - H[i])
            l.append(dp[i-k] + d)
    if len(l) > 0:
        dp[i] = min(l)
    else:
        dp[i] = 0

print(dp[-1])

### FIXED CODE ###

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

dp = [0] * N
dp[1] = abs(H[1]-H[0])

for i in range(2, N):
    dp[i] = min([dp[i-k] + abs(H[i-k]-H[i]) for k in range(1, 1+K) if 0 <= i-k])

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in a:
        cnt = 0
        for j in range(n):
            if i % a[j] == 0:
                cnt += 1
        if cnt == 1:
            ans += 1
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_s = sorted(a)
    a_set = set(a_s)
    maxv = max(a)
    res = [0] * maxv
    rep = 0
    for i in a_s:
        if i in a_set:
            if res[i-1] == 0:
                for j in range(i, maxv+1, i):
                    res[j-1] += 1
            else:
                res[i-1] +=1
    cnt = 0
    for i in range(n):
        if res[a[i]-1] == 1:
            cnt += res[a[i]-1]
    print(cnt)

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

def main(): 
    n = int(input())
    s = sorted([sorted(input()) for _ in range(n)])
    
    cnt = 0
    for i in range(n):
        for j in range(i+1,n):
            if s[i] == s[j]:
                cnt += 1
            else:
                break

    print(cnt)


if __name__ == "__main__":
    main() 

### FIXED CODE ###

def main(): 
    n = int(input())
    s = [''.join(sorted(input())) for _ in range(n)]
    ans = 0
    dic = {}
    for si in s:
        if si in dic:
            ans += dic[si]
            dic[si] += 1
        else:
            dic[si] = 1
    print(ans)


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

N=int(input())
table=[[int(i) for i in input().split()] for j in range(0,N)]

for i in range(0,N-1):
    for j in range(0,10**9):
        if table[i][0]<=j*table[i+1][0]:
            for l in range(j,10**9):
                if table[i][1]<=l*table[i+1][1]:
                    table[i+1][1]=l*table[i+1][1]
                    table[i+1][0]=l*table[i+1][0]
                    break
                else:
                    pass
            break
        else:
            pass

print(table[N-1][0]+table[N-1][1])


### FIXED CODE ###

N=int(input())
table=[[int(i) for i in input().split()] for j in range(0,N)]

for i in range(0,N-1):
    a=table[i][0]//table[i+1][0]
    A=table[i][0]%table[i+1][0]
    b=table[i][1]//table[i+1][1]
    B=table[i][1]%table[i+1][1]
    if a>b and A==0:
        table[i+1][0]=a*table[i+1][0]
        table[i+1][1]=a*table[i+1][1]
    elif a>b and not A==0:
        table[i+1][0]=(a+1)*table[i+1][0]
        table[i+1][1]=(a+1)*table[i+1][1]
    elif a<b and B==0:
        table[i+1][0]=b*table[i+1][0]
        table[i+1][1]=b*table[i+1][1]
    elif a<b and not B==0:
        table[i+1][0]=(b+1)*table[i+1][0]
        table[i+1][1]=(b+1)*table[i+1][1]
    elif a==b and A==0 and B==0:
        table[i+1][0]=a*table[i+1][0]
        table[i+1][1]=a*table[i+1][1]
    elif a==b and not A==0 and B==0:
        table[i+1][0]=(a+1)*table[i+1][0]
        table[i+1][1]=(a+1)*table[i+1][1]
    elif a==b and not B==0 and A==0:
        table[i+1][0]=(a+1)*table[i+1][0]
        table[i+1][1]=(a+1)*table[i+1][1]
    elif a==b and not B==0 and not A==0:
        table[i+1][0]=(a+1)*table[i+1][0]
        table[i+1][1]=(a+1)*table[i+1][1]

print(table[N-1][0]+table[N-1][1])
### BUGGY CODE ###

#!/usr/bin/env python3

def func(n):
    cnt = 0
    for x in range(1, int(n*.5)+1):
        if x * x > n:
            break
        for y in range(1, int(n*.5)+1):
            if y * y > n:
                break
            for z in range(1, int(n*.5)+1):
                if z * z > n:
                    break
                if x * x + y * y + z * z + x * y + y * z + z * x == n:
                    cnt += 1
                    break
    return cnt


def main():
    N = int(input())

    for i in range(1, N + 1):
        print(func(i))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())

    ans = [0] * (N + 1)

    for x in range(1, 100):
        for y in range(1, 100):
            for z in range(1, 100):
                f = x * x + y * y + z * z + x * y + y * z + z * x
                if f < N + 1:
                    ans[f] += 1
    ans.remove(0)
    print('\n'.join(map(str, ans)))


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

def plus(a,b):
    c=a[0]*b[1]+b[0]*a[1]
    d=a[1]*b[1]
    return (c,d)
def div(a,b):
    c=a[0]*b[1]
    d=a[1]*b[0]
    return (c,d)
def times(a,b):
    c=a[1]*b[1]
    d=a[0]*b[0]
    return (c,d)
def minus(a,b):
    c=a[0]*b[1]-b[0]*a[1]
    d=a[1]*b[1]
    return (c,d)

N,M=map(int,input().split())
x=[0 for i in range(M)]
y=[0 for i in range(M)]
for i in range(M):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
a=[(0,1) for i in range(N)]
a[0]=(1,1)
b=[1 for i in range(N)]
for i in range(M):
    b[x[i]]-=1
    b[y[i]]+=1
    t=a[x[i]]
    a[x[i]]=minus(a[x[i]],div(t,(b[x[i]]+1,1)))
    a[y[i]]=plus(a[y[i]],div(t,(b[x[i]]+1,1)))
n=0
for i in range(N):
    if a[i][0]!=0:
        n+=1
print(n)


### FIXED CODE ###

N,M=map(int,input().split())
x=[0 for i in range(M)]
y=[0 for i in range(M)]
for i in range(M):
    x[i],y[i]=map(int,input().split())
    x[i]-=1
    y[i]-=1
a=[0 for i in range(N)]
a[0]=1
b=[1 for i in range(N)]
for i in range(M):
    b[x[i]]-=1
    b[y[i]]+=1
    if a[x[i]]==1:
        a[y[i]]=1
    if b[x[i]]==0:
        a[x[i]]=0
print(sum(a))
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
count = 0
 
for i in range(N):
  for j in range(i + 1, N):
    for k in range(j + 1, N):
      if L[k] < L[i] + L[j]:
        count += 1
print(count)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
count = 0
from bisect import bisect_left
for i in range(N - 2):
  for j in range(i + 1, N - 1):    
      count += bisect_left(L, L[i] + L[j]) - 1 - j
      
print(count)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = list(input())
lr_list = [0] * Q

for i in range(Q):
    lr_list[i] = list(map(int, input().split()))

a_list = []
for i in range(len(S)):
    if S[i] == "A" and i != len(S) - 1:
        if S[i + 1] == "C":
            a_list.append(i)
counter = 0
for i in range(Q):
    for j in range(len(a_list)):
        if lr_list[i][0] - 1 <= a_list[j] and a_list[j]+1 <= lr_list[i][1]-1:
            counter += 1
    print(counter)
    counter=0


### FIXED CODE ###

N, Q = map(int, input().split())
S = list(input())
lr_list = [0] * Q

a_list = []
for i in range(len(S)):
    if S[i] == "A" and i != len(S) - 1:
        if S[i + 1] == "C":
            S[i]="a"

ti=[0]*N

for i in range(1,N):
    if S[i-1]=="a":
        ti[i]=ti[i-1]+1
    else:
        ti[i]=ti[i-1]

for i in range(Q):
    l,r= list(map(int, input().split()))
    print(ti[r-1]-ti[l-1])
### BUGGY CODE ###

a, b = map(int, input().split())
ans = a
for ab in range(a + 1, b + 1):
    ans = ans ^ ab
print(ans)

### FIXED CODE ###

a, b = map(int, input().split())
if a == b:
    ans = a
elif a % 2 == 0:
    if (b - a) % 4 == 0:
        ans = 0 ^ b
    elif (b - a) % 4 == 2:
        ans = 1 ^ b
    elif (b - a) % 4 == 1:
        ans = 1
    else:
        ans = 0
else:
    if (b - a) % 4 == 0:
        ans = a ^ 0
    elif (b - a) % 4 == 2:
        ans = a ^ 1
    elif (b - a) % 4 == 1:
        ans = a ^ 0 ^ b
    else:
        ans = a ^ 1 ^ b
print(ans)
### BUGGY CODE ###

from bisect import bisect_right

def div_ceil(x, y): return (x + y - 1) // y

N, D, A = map(int, input().split())
monsters = [list(map(int, input().split())) for _ in range(N)]
monsters = sorted(monsters, key=lambda x: x[0])
position = [x for x, _ in monsters]
ans = 0
for i, m in enumerate(monsters):
    x, hp = m
    if hp <= 0: continue
    j = bisect_right(position, x + 2*D)
    attack = div_ceil(hp, A)
    ans += attack
    damage = attack * A
    for k in range(i+1, min(j, N)):
        monsters[k][1] -= damage
print(ans)

### FIXED CODE ###

from bisect import bisect_right

def div_ceil(x, y): return (x + y - 1) // y

N, D, A = map(int, input().split())
monsters = [list(map(int, input().split())) for _ in range(N)]
monsters = sorted(monsters, key=lambda x: x[0])
position = [x for x, _ in monsters]
damage = [0] * (N+2)
ans = 0
for i, [x, hp] in enumerate(monsters, 1):
    damage[i] += damage[i-1]
    if damage[i] >= hp: continue
    hp -= damage[i]
    j = bisect_right(position, x + 2*D) + 1
    attack = div_ceil(hp, A)
    ans += attack
    dam = attack * A
    # imos's method
    damage[i] += dam
    damage[j] -= dam
print(ans)
### BUGGY CODE ###

import math


def read():
    N, P = list(map(int, input().strip().split()))
    return N, P


def solve(N, P):
    v3 = math.floor(P**(1/N)) + 1
    for v in range(v3, 0, -1):
        if P % (v**N) == 0:
            return v
    return 1


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))


### FIXED CODE ###

import math


def read():
    N, P = list(map(int, input().strip().split()))
    return N, P


def solve(N, P):
    # problem constraint
    if N >= 40:
        return 1
    # solve
    v3 = math.floor(P**(1/N)) + 1
    for v in range(v3, 0, -1):
        if P % (v**N) == 0:
            return v
    return 1


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))
### BUGGY CODE ###

A, B, N = map(int, input().split())
result = []
cnt = 0

for _ in range(N):
  cnt += 1
  result.append(int(A*cnt/B)-A*int(cnt/B))
  
print(max(result))

### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10**7)
n,q = map(int,input().split())
g = [[] for i in range(n)]
c = [0]*n
reach = [False]*n
for i in range(n-1):
    a,b = map(lambda x: int(x)-1,input().split())
    g[a].append(b)
    g[b].append(a)

for i in range(q):
    p,x = map(int,input().split())
    c[p-1] += x

def dfs(v):
    reach[v] = True
    for i in g[v]:
        if not reach[i]:
            c[i] += c[v]
            dfs(i)

reach[0] = True
dfs(0)
print(*c)

### FIXED CODE ###

n,q = map(int,input().split())
g = [[] for i in range(n)]
c = [0]*n
reach = [False]*n
for i in range(n-1):
    a,b = map(lambda x: int(x)-1,input().split())
    g[a].append(b)
    g[b].append(a)

for i in range(q):
    p,x = map(int,input().split())
    c[p-1] += x

reach[0] = True
q = [0]
while q:
    cur = q.pop()
    reach[cur] = True
    for i in g[cur]:
        if not reach[i]:
            c[i] += c[cur]
            q.append(i)
print(*c)
### BUGGY CODE ###

N=int(input())
p = 1

for i in range(N + 1):
  if i == 0:
    continue

  p *= i

print(p % (1000000000 + 7))

### FIXED CODE ###

N=int(input())
p = 1
C = 10**9+7

for i in range(N + 1):
  if i == 0:
    continue

  p *= i
  p %= C

print(p)