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

import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def is_between(x1, x2, x):
    if x >= x1 and x <= x2:
        return True
    elif x <= x1 and x >= x2:
        return True
    else:
        return False

def count(x1, x2, y1, y2):
    num = 0
    for i in range(N):
        if is_between(x1, x2, points[i][0]) and is_between(y1, y2, points[i][1]):
            num += 1
    return num

ans = INF
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                if count(to_search_x[i], to_search_x[j], to_search_y[k], to_search_y[l]) >= K:
                    ans = min(ans, abs((to_search_x[i]-to_search_x[j])*(to_search_y[k]-to_search_y[l])))

print(ans)


### FIXED CODE ###

import math
INF = 10000000000000000000000000000000000
N, K = map(int, input().split())
points = []
to_search_x = []
to_search_y = []
points_matrix = [[0]*(N+1) for i in range(N+1)]
for i in range(N):
    xi, yi = map(int, input().split())
    points.append([xi, yi])
    to_search_x.append(xi)
    to_search_y.append(yi)

to_search_x.sort()
to_search_y.sort()

def count(xmin, xmax, ymin, ymax):
    num = 0
    for i in range(N):
        x,y = points[i]
        if (xmin <= x and xmax >= x) and (ymin <= y and ymax >= y):
            num += 1
    return num

for n in range(N):
    for i in range(N):
        for j in range(N):
            if points[n][0] <= to_search_x[i] and points[n][1] <= to_search_y[j]:
                points_matrix[i+1][j+1] += 1

ans = INF
for i in range(N):
    for j in range(i,N):
        for k in range(N):
            for l in range(k,N):
                if (points_matrix[i][k] + points_matrix[j+1][l+1] - points_matrix[i][l+1] - points_matrix[j+1][k]) >= K:
                    ans = min(ans, (to_search_x[j]-to_search_x[i])*(to_search_y[l]-to_search_y[k]))

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

k, s = input().split()
k, s = int(k), int(s)
ans = 0
for x in range(0, k+1):
  for y in range(0, k+1):
    for z in range(0, k+1):
      if x+y+z==s:
        ans += 1
        break
print(ans)

### FIXED CODE ###

k, s = input().split()
k, s = int(k), int(s)
ans = 0
for x in range(0, k+1):
  for y in range(0, k+1):
      if -1<s-x-y<k+1:
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
xy = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*xy)]

sum = 0

for cnt_q in range(q):
    sum = 0
    for cnt_n in range(n):
        if a[cnt_n] == b[cnt_q]:
            a[cnt_n] = c[cnt_q]
    for num in range(n):
        sum += a[num]
    print(sum)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
xy = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*xy)]

ans = 0

sum_all = 0
for cnt in range(n):
    sum_all += a[cnt]

a = sorted(a)
list_a_num = [0]*(10**5 + 1)
for cnt in range(n):
    list_a_num[a[cnt]] += 1

for cnt in range(q):
    sum_all += (c[cnt] - b[cnt]) * list_a_num[b[cnt]]
    list_a_num[c[cnt]] += list_a_num[b[cnt]]
    list_a_num[b[cnt]] = 0
    print(sum_all)
### BUGGY CODE ###

def resolve():
    ss = input()
 
    dp = [0] * 13
    dp[0] = 1
 
    mod = 10 ** 9 + 7
    mul = 1
 
    # 後ろから解く
    for s in ss[::-1]:
        next_dp = [0] * 13
 
        if s == '?':
            for num in range(10):
                for i in range(13):
                    next_dp[(num * mul + i) % 13] += dp[i]
                    next_dp[(num * mul + i) % 13] %= mod
        else:
            num = int(s)
            for i in range(13):
                next_dp[(num * mul + i) % 13] += dp[i]
                next_dp[(num * mul + i) % 13] %= mod
 
        mul *= 10
        mul %= 13
        dp = next_dp
 
    print(dp[5])
    
resolve()

### FIXED CODE ###

def resolve():
    ss = input()

    dp = [0] * 13
    dp[0] = 1

    mod = 10 ** 9 + 7
    mul = 1

    # 後ろから解く
    for s in ss[::-1]:
        next_dp = [0] * 13

        if s == '?':
            for num in range(10):
                for i in range(13):
                    next_dp[(num * mul + i) % 13] += dp[i]
                    next_dp[(num * mul + i) % 13] %= mod
        else:
            num = int(s)
            for i in range(13):
                next_dp[(num * mul + i) % 13] += dp[i]
                next_dp[(num * mul + i) % 13] %= mod

        mul *= 10
        mul %= 13
        dp = next_dp

    print(dp[5])
    
resolve()
### BUGGY CODE ###

from itertools import permutations

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

D = []
for i in range(C):
    D.append(list(map(int, input().split())))

remains = {0: [], 1: [], 2: []}

for i in range(1, N+1):
    line = list(map(int, input().split()))
    for j in range(N):
        remains[(i+j+1)%3].append(line[j])

INF = 65535

def recolor(x, y):
    return D[x-1][y-1]

answer = INF
for choice in permutations(list(range(1, C+1)), 3):
    _answer = 0
    for i in range(3):
        _answer += sum([recolor(r, choice[i]) for r in remains[i] if choice[i] != r])
    answer = min(answer, _answer)

print(answer)

### FIXED CODE ###

from itertools import permutations
from collections import defaultdict

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

remains = {0: defaultdict(int), 1: defaultdict(int), 2: defaultdict(int)}
for i in range(1, N+1):
    line = list(map(int, input().split()))
    for j in range(N):
        remains[(i+j+1)%3][line[j]] += 1

INF = float('inf')

def recolor(x, y, count):
    return D[x-1][y-1] * count

answer = INF
for choice in permutations(range(1, C+1), 3):
    _answer = 0
    for i, c in enumerate(choice):
        _answer += sum([recolor(r, c, remains[i][r]) for r in remains[i] if c != r])
    answer = min(answer, _answer)

print(answer)
### BUGGY CODE ###

#abc177 e
import sys,math,collections,itertools
input = sys.stdin.readline

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)

    if temp!=1:
        arr.append(temp)

    if arr==[]:
        arr.append(n)
    return arr


N=int(input())
A=list(map(int,input().split()))
num = [0]*(10**6+1)

fact = [1]

for a in A:
    if a != 1:
        fact += factorization(a)
mn= collections.Counter(fact).most_common()[0][1]

if mn == 1:
    print('pairwise coprime')
elif mn ==N:
    print('not coprime')
else:
    print('setwise coprime')


### FIXED CODE ###

#abc177 e
import sys,math,collections,itertools
import functools
input = sys.stdin.readline


N=int(input())
A=list(map(int,input().split()))
fact = set()
for a in A:
    if a==1:
        fact.add(1)
        continue
    if a%2 == 0 and 2 in fact:
        break
    while a%2==0:
        fact.add(2)
        a//=2
            
    i =3
    while i*i <= a:
        if a%i ==0 and i in fact:
            break
        while a%i==0:
            fact.add(i)
            a//=i
        else:
            i +=2
    else:
        if a != 1:
            if a in fact:
                break
            fact.add(a)
        continue
    break
else:
    print('pairwise coprime')
    exit()
if functools.reduce(math.gcd,A)!=1:
    print('not coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

S = input()
N = len(S)
i = 0
T = ""
while i <= N-2:
    if S[i] == 'B' and S[i+1] == 'C':
        T += 'D'
        i += 1
    else:
        T += S[i]
    i += 1


N = len(T)
ans = 0
l = 0
while l < N:

    if T[l] == 'B' or T[l] == 'C':
        l += 1
        continue
    
    r = l
    tmp = ''
    while r < N and (T[r] == 'A' or T[r] == 'D'):
        tmp += T[r]
        r += 1
    
    M = len(tmp)
    D_count = [0]*(M+1)
    for i in range(M-1, -1, -1):
        D_count[i] = D_count[i+1]
        if tmp[i] == 'D':
            D_count[i] += 1
    
    for i in range(M):
        if tmp[i] == 'A':
            ans += D_count[i]
    
    if r == N:
        break
    else:
        l = r+1

print(ans)





### FIXED CODE ###

S = input()
N = len(S)
i = 0
T = []
while i <= N-2:
    if S[i] == 'B' and S[i+1] == 'C':
        T.append('D')
        i += 1
    else:
        T.append(S[i])
    i += 1

T = "".join(T)

N = len(T)
ans = 0
l = 0
while l < N:

    if T[l] == 'B' or T[l] == 'C':
        l += 1
        continue
    
    r = l
    tmp = []
    while r < N and (T[r] == 'A' or T[r] == 'D'):
        tmp.append(T[r])
        r += 1
    
    M = len(tmp)
    D_count = [0]*(M+1)
    for i in range(M-1, -1, -1):
        D_count[i] = D_count[i+1]
        if tmp[i] == 'D':
            D_count[i] += 1
    
    for i in range(M):
        if tmp[i] == 'A':
            ans += D_count[i]
    
    if r == N:
        break
    else:
        l = r+1

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

import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

#########################
n = int(input())

#隣接リストの作成 edge[i]:[コスト,行先]
edge = [[] for i in range(n)]
x_sort = [] #[Xi,Yi,点番号]
y_sort = [] #[Yi,Xi,点番号]
for i in range(n):
    X,Y = map(int,input().split())
    x_sort.append([X,Y,i])
    y_sort.append([Y,X,i])
x_sort.sort()
y_sort.sort()
for i in range(1,n):
    edge[x_sort[i][2]].append([min(abs(x_sort[i][0]-x_sort[i-1][0]),abs(x_sort[i][1]-x_sort[i-1][1])),x_sort[i-1][2]])
    edge[x_sort[i-1][2]].append([min(abs(x_sort[i][0]-x_sort[i-1][0]),abs(x_sort[i][1]-x_sort[i-1][1])),x_sort[i][2]])
    edge[y_sort[i][2]].append([min(abs(y_sort[i][0]-y_sort[i-1][0]),abs(y_sort[i][1]-y_sort[i-1][1])),y_sort[i-1][2]])
    edge[y_sort[i][2]].append([min(abs(y_sort[i][0]-y_sort[i-1][0]),abs(y_sort[i][1]-y_sort[i-1][1])),y_sort[i-1][2]])
print(prim_heap())

### FIXED CODE ###

import heapq
def prim_heap():
    used = [True] * n #True:不使用
    edgelist = []
    for e in edge[0]:
        heapq.heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,e)
        res += minedge[0]
    return res

#########################
n = int(input())

#隣接リストの作成 edge[i]:[コスト,行先]
edge = [[] for i in range(n)]
p=[]
edge=[[] for i in range(n)]
for i in range(n):
    p.append(tuple(map(int,input().split()))+tuple([i]))
x_sorted=sorted(p,key=lambda x:x[0])
y_sorted=sorted(p,key=lambda x:x[1])
for i in range(n-1):
    edge[x_sorted[i][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i+1][2]))
    edge[x_sorted[i+1][2]].append((x_sorted[i+1][0]-x_sorted[i][0],x_sorted[i][2]))
    edge[y_sorted[i][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i+1][2]))
    edge[y_sorted[i+1][2]].append((y_sorted[i+1][1]-y_sorted[i][1],y_sorted[i][2]))

print(prim_heap())
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=10**18

cnt=1
for i in range(n):
    cnt*=a[i]

if cnt>mod:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
mod=10**18

cnt=1
for i in range(n):
    cnt*=a[i]
    if cnt>mod:
        print(-1)
        exit()

print(cnt)
### BUGGY CODE ###

x,k,d=[int(i) for i in input().split()]

x=abs(x)

t=x

if k%2==1:
    t-=d
    k-=1

min=abs(t)

if x-k*d<0:
    k-=(x/(d*2))*2

while(-x<t and k>0):
    t-=d*2
    k-=2
    if min < abs(t):
        break
    else:
        min=abs(t)

print(min)


### FIXED CODE ###

x,k,d=[int(i) for i in input().split()]

x=abs(x)

a=int(x/d)


if a>k:
    a=k

k-=a

x-=a*d

if k%2==1:
    x=abs(x-d)
    k-=1

print(x)
### BUGGY CODE ###

n = int(input())
d = input().split()
m = int(input())
t = input().split()

for x in t:
    if x in d:
        d.remove(x)
    else:
        print('NO')
        exit()

print('YES')


### FIXED CODE ###

n = int(input())
d = input().split()
m = int(input())
t = input().split()

d.sort()
t.sort()
a = 0

for x in t:
    for i in range(a, n):
        if d[i] > x:
            print('NO')
            exit()
        if x == d[i]:
            a = i+1
            break

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

n = int(input())
a = list(input().split())
b = [int(i) for i in a]
ans=0
def cal2(k):
    return k /2

while True:
    if  sum(b)% 2 == 0:
        b = list(map(cal2,b))
        ans+=1
else:
    print(ans)
print(ans)

### FIXED CODE ###

import numpy as np
N=int(input())
A=list(map(int,input().split()))
A=np.array(A)
ans=2**9
for i in A:
  cnt=0
  while i%2==0:
    i=i/2
    cnt+=1
  if ans > cnt:
    ans=cnt
    
print(ans)
### BUGGY CODE ###

import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

A,B,N = LI()
ans = 0

for x in range(N+1):
    ans = max(ans,math.floor(A*x/B) - A * math.floor(x/B))

print(ans)

### FIXED CODE ###

# 具体例を試す
import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

A,B,N = LI()
# ans = 0

# a = [0]*N

# for x in range(1,N+1):
#     # ans = max(ans,math.floor(A*x/B) - A * math.floor(x/B))
#     a[x-1]=math.floor(A*x/B) - A * math.floor(x/B)

x = min(N,B-1)
ans = math.floor(A*x/B) - A * math.floor(x/B)
print(ans)
### BUGGY CODE ###

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

for i in range(N):
  for j in range(N):
    if i==j:
      pass
    elif A[i]%A[j]==0:
      break
  else:
    x+=1

print(x)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
AM=max(A)+1
B=[0]*AM
x=0
for i in A:
  for j in range(i,AM,i):
    B[j]+=1
for i in A:
  if B[i]==1:
    x+=1
print(x)
### BUGGY CODE ###

n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")

box = [0] * (maxbit + 1)

def f(i):
  cnt = 0
  while i > 0:
    if box[i] != 0:
      return box[i] + cnt
    i %= bin(i).count("1")
    cnt += 1
  return cnt

for i in range(1, min(maxbit + 1, 200000)):
  box[i] = f(i)

for i in range(lenx):
  if x[i] == "0":
    mb = maxbit + 1
    t = x10 + 2 ** (lenx - 1 - i)
  else:
    mb = maxbit - 1
    t = x10 - 2 ** (lenx - 1 - i)
  # print(t, mb)
  if t == 0:
    print(0)
  else:
    t %= mb 
    if t == 0:
      print(1)
    else:
      ans = f(t) + 1 
      box[t] = ans - 1
      print(ans)

### FIXED CODE ###

n = int(input())
x = input()
x10 = int(x, 2)
lenx = len(x)

maxbit = x.count("1")
xc0 = x10 % (maxbit + 1)
xc1 = x10 % (maxbit - 1) if maxbit > 1 else 0

def f(ii):
  cnt = 0
  while ii > 0:
    ii %= bin(ii).count("1")
    cnt += 1
  return cnt

for i in range(lenx):
  if x[i] == "0":
    t = xc0 + pow(2, (lenx - 1 - i), maxbit + 1)
    ans = f(t % (maxbit + 1)) + 1
  else:
    if maxbit - 1 == 0:
      ans = 0
    else:
      t = xc1 - pow(2, (lenx - 1 - i), maxbit - 1)
      ans = f(t % (maxbit - 1)) + 1
  print(ans)
### BUGGY CODE ###

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

def bisec(i,k): #ギリギリokなj<=j_を探す
    ci = i
    ck = k
    i+=1
    k-=1
    j = (i+k)//2
    while k-i>1:
        if l[ci]+l[j]>l[ck]:
            k = j
            j = (i+k)//2
        else:
            i = j+1
            j = (i+k)//2
    if l[ci]+l[i]>l[ck]:
        return i
    elif l[ci]+l[i+1]>l[ck]:
        return i+1
    else:
        return -1

for i in range(n):
#     for j in range(i+1,n):  i<j<kでl[i]+l[j]>l[k]を満たすものを二分探索
    for k in range(i+2,n):
        j = bisec(i,k)
        if j>=0:
            ans += k-j
print(ans)

### FIXED CODE ###

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

def bisec(i,k): #ギリギリokなj<=j_を探す
    ci = i
    ck = k
    i+=1
    k-=1
    j = int((i+k)/2)
    while k-i>1:
        if l[ci]+l[j]>l[ck]:
            k = j
            j = int((i+k)/2)
        else:
            i = j+1
            j = int((i+k)/2)
    if l[ci]+l[i]>l[ck]:
        return True,i
    elif l[ci]+l[i+1]>l[ck]:
        return True,i+1
    else:
        return False,-1

for i in range(n):
    for k in range(i+2,n):
        f,j = bisec(i,k)
        if f:
            ans += k-j
print(ans)
### BUGGY CODE ###

N, M, K = list(map(int, input().split(" ")))
A = list(map(int, input().split(" ")))
B = list(map(int, input().split(" ")))
max = 0
memo = {"A":0, "B":0, "time":0}
for i in range(len(A)+1):
  for j in range(len(B)+1):
    time = 0
    if i > 0:
    	time += sum(A[:i])
    if j > 0:
    	time += sum(B[:j])
    if time > K:
      break
    elif max < i+j:
      max = i+j
      memo["A"] = i
      memo["B"] = j
      memo["time"] = time
      
print(max) # , memo)

### FIXED CODE ###

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

sumA = [0] * (N+1)
sumB = [0] * (M+1)
for i in range(N):
  sumA[i+1] = sumA[i] + A[i]
for i in range(M):
  sumB[i+1] = sumB[i] + B[i]

b_i = M
max_count = 0
for i in range(N+1):
  a = sumA[i]
  if a > K:
    continue
  if b_i>0:
    while a + sumB[b_i] > K:
      b_i -= 1
      if b_i==0:
        break
  max_count = max(max_count, i + b_i)
print(max_count)
### BUGGY CODE ###

def main():
    import numpy as np
    import sys
    buf = sys.stdin.buffer


    n, t = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    shops = []
    shopsA0 = []

    for a, b in zip(m, m):
        if a == 0:
            shopsA0.append(b+1)
        else:
            shops.append([a/(b + 1), a, b])

    shops.sort(reverse=True)
    shopsA0.sort()

    DP = np.array([t+10]*29, dtype=np.int64)
    DP[0] = 0

    for _, a, b in shops:
        np.minimum(DP[1:], (DP[:-1]+1)*(a+1)+b, out=DP[1:])

    cumA0 = np.cumsum(shopsA0, dtype=np.int64)

    DP = DP[DP <= t]
    DPA0 = np.searchsorted(cumA0, t-DP, side='right')
    ans = np.arange(len(DP)) + DPA0
    print(ans.max())


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import itertools
    import sys
    buf = sys.stdin.buffer


    n, t = map(int, buf.readline().split())
    m = map(int, buf.read().split())
    shops = []
    shopsA0 = [0]

    for a, b in zip(m, m):
        if a == 0:
            shopsA0.append(b + 1)
        else:
            shops.append([a / (b + 1), a, b])

    shopsA0.sort()
    shops.sort(reverse=True)


    DP = [t+10] * 30
    DP[0] = 0

    for _, a, b in shops:
        for num in range(28, -1, -1):
            candidate = (DP[num]+1) * (a+1) + b
            if candidate < DP[num+1]:
                DP[num+1] = candidate

    cumA0 = list(itertools.accumulate(shopsA0))

    ans = [0]
    count_A0 = len(cumA0) - 1
    for count, spend_time in enumerate(DP):
        residue = t - spend_time
        if residue < 0:
            break
        while count_A0 > 0 and cumA0[count_A0] > residue:
            count_A0 -= 1
        ans.append(count_A0 + count)
    print(max(ans))


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

import sys
readline=sys.stdin.readline

N = int(readline())

DIV = 10 ** 9 + 7

dp = [[0] * 4 for i in range(N + 1)]

dp[0][0] = 1

for i in range(1, N + 1):
  dp[i][0] += dp[i - 1][0] * 8
  dp[i][0] %= DIV
  
  dp[i][1] += dp[i - 1][0] + dp[i - 1][1] * 9
  dp[i][1] %= DIV
  
  dp[i][2] += dp[i - 1][0] + dp[i - 1][2] * 9
  dp[i][2] %= DIV
  
  dp[i][3] += dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] * 10
  dp[i][3] %= DIV
  
print(dp[-1][3])


### FIXED CODE ###

import sys
readline=sys.stdin.readline

N = int(readline())

DIV = 10 ** 9 + 7

# dp[i][j][k] = i - 1桁目で、すでに0が出た(j), すでに9が出た(k)

dp = [[[0] * 2 for j in range(2)] for i in range(N + 1)]

dp[0][0][0] = 1

for i in range(1, N + 1):
  dp[i][0][0] += dp[i - 1][0][0] * 8 # まだ0も9も出ない
  dp[i][0][0] %= DIV
  
  dp[i][1][0] += dp[i - 1][0][0] # 0が出た
  dp[i][1][0] += dp[i - 1][1][0] * 9 # 9以外何が出てもよい
  dp[i][1][0] %= DIV
  
  dp[i][0][1] += dp[i - 1][0][0] # 9が出た
  dp[i][0][1] += dp[i - 1][0][1] * 9 # 0以外何が出てもよい
  dp[i][0][1] %= DIV
  
  dp[i][1][1] += dp[i - 1][1][0] # 9が出た
  dp[i][1][1] += dp[i - 1][0][1] # 0が出た
  dp[i][1][1] += dp[i - 1][1][1] * 10 # 何が出てもよい
  dp[i][1][1] %= DIV
  
print(dp[-1][1][1])
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import Counter
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = []
    for i in range(N):
        x, h = MI()
        Enemy.append([x, h])
    Enemy.sort(key=lambda list: list[0])
    Enemy_Ran = []
    for ene in Enemy:
        Enemy_Ran.append(ene[0])


    cnt = 0
    for i in range(N):
        if Enemy[i][1] <= 0:
            continue
        else:
            ata = math.ceil(Decimal(Enemy[i][1]) / Decimal(A))
            cnt += ata
            ran = Enemy[i][0] + 2 * D
            ran_i = bisect.bisect_right(Enemy_Ran, ran)
            dam = ata * A
            for j in range(i + 1, ran_i):
                if Enemy[j][1] <= 0:
                    continue
                else:
                    Enemy[j][1] -= dam

    print(cnt)


if __name__ == "__main__":
    main()



### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import defaultdict
from collections import deque
import bisect
from decimal import *
def main():
    N, D, A = MI()
    Enemy = defaultdict()
    Enemy_ran = []
    for i in range(N):
        x, h = MI()
        Enemy[x] = h
        Enemy_ran.append(x)
    Enemy_ran.sort()
    cnt = 0
    dam_list = deque()
    dam_all = 0
    for i in range(N):
        x = Enemy_ran[i]
        while len(dam_list) != 0 and i >= dam_list[0][0]:
            dam_all -= dam_list.popleft()[1]
        HP = Enemy[x] - dam_all
        if HP <= 0:
            continue
        else:
            ata = math.ceil(Decimal(HP) / Decimal(A))
            cnt += ata
            ran = x + 2 * D
            y = bisect.bisect_right(Enemy_ran, ran)
            dam = ata * A
            dam_list.append((y, dam))
            dam_all += dam


    print(cnt)


if __name__ == "__main__":
    main()