Problem:
 Score : 600 points    Problem Statement Silver Fox is fighting with N monsters.  The monsters are standing in a row, and we can assume them to be standing on a number line. The i -th monster, standing at the coordinate X_i , has the health of H_i .  Silver Fox can use bombs to attack the monsters.
Using a bomb at the coordinate x decreases the healths of all monsters between the coordinates x-D and x+D (inclusive) by A .
There is no way other than bombs to decrease the monster's health.  Silver Fox wins when all the monsters' healths become 0 or below.  Find the minimum number of bombs needed to win.      Constraints  1 \leq N \leq 2 \times 10^5  0 \leq D \leq 10^9  1 \leq A \leq 10^9  0 \leq X_i \leq 10^9  1 \leq H_i \leq 10^9  X_i are distinct.  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  D  A  X_1  H_1  :  X_N  H_N       Output Print the minimum number of bombs needed to win.        Sample Input 1 3 3 2
1 2
5 4
9 2      Sample Output 1 2  First, let us use a bomb at the coordinate 4 to decrease the first and second monsters' health by 2 .  Then, use a bomb at the coordinate 6 to decrease the second and third monsters' health by 2 .  Now, all the monsters' healths are 0 .
We cannot make all the monsters' health drop to 0 or below with just one bomb.       Sample Input 2 9 4 1
1 5
2 4
3 3
4 2
5 1
6 2
7 3
8 4
9 5      Sample Output 2 5  We should use five bombs at the coordinate 5 .       Sample Input 3 3 0 1
300000000 1000000000
100000000 1000000000
200000000 1000000000      Sample Output 3 3000000000  Watch out for overflow.

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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


def solve_binary(mid,k):
    return k < XH[mid][0]

def binary_search(s,n,k):
    ok=n
    ng=s
    while abs(ok-ng)>1:
        mid=(ok+ng)//2
        if solve_binary(mid,k):
            ok=mid
        else:
            ng=mid
    return ok

n,D,A=map(int,input().split())
XH=[tuple(map(int,input().split())) for i in range(n)]
XH.sort(key=lambda tup: tup[0])
XH.append((inf,0))
data=[0]*(n+1)





for i in range(n):
    xi,hi = XH[i]
    hi-=data[i]
    K=max(0,ceil(hi,A)*A); count += max(0,ceil(hi,A))
    data[i]+=K; data[binary_search(i,n,xi+2*D)]-=K
    data[i+1]+=data[i]
print(count)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, D, A, XH):
    XH.sort()

    q = deque()
    ans = 0
    dmg = 0
    for x, h in XH:
        while q and q[0][0] < x:
            _, d = q.popleft()
            dmg -= d
        if h <= dmg:
            continue
        a = -(-(h - dmg) // A)
        ans += a
        q.append((x+2*D, a*A))
        dmg += a*A
    return ans


def main():
    N, D, A = read_int_n()
    XH = [read_int_n() for _ in range(N)]
    print(slv(N, D, A, XH))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, D, A, XH):
    XH.sort()
    X = [x for x, _ in XH]
    H = [h for _, h in XH]

    q = deque()
    ans = 0
    dmg = 0
    for x, h in XH:
        while q and q[0][0] < x:
            _, d = q.popleft()
            dmg -= d
        if h <= dmg:
            continue
        a = -(-(h - dmg) // A)
        ans += a
        q.append((x+2*D, a*A))
        dmg += a*A
    return ans


def main():
    N, D, A = read_int_n()
    XH = [read_int_n() for _ in range(N)]
    print(slv(N, D, A, XH))


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


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


N, D, A = inpl()
XH = [inpl() for i in range(N)]
XH.sort()


bomb = [(h + A - 1) // A for x, h in XH]

ans = 0
dq = deque()
s_i = 0
sum_q = 0
for i in range(N):
    while dq and dq[0][1] < XH[i][0]:
        b, _ = dq.popleft()
        sum_q -= b

    bomb[i] -= sum_q
    if bomb[i] <= 0:
        pass
    else:
        ans += bomb[i]
        sum_q += bomb[i]
        dq.append([bomb[i], XH[i][0] + 2 * D])

print(ans)

Solution (Python):
import bisect
n, d, a = map(int, input().split())
XH = sorted([list(map(int, input().split())) for _ in range(n)])
X, H = zip(*XH)
K = [-(-i//a) for i in H]
L = [0]*(n+2)
ans = 0
for i in range(n):
  L[i+1] += L[i]
  s = max(K[i]-L[i+1], 0)
  ans += s
  L[i+1] += s
  L[bisect.bisect_right(X, X[i]+2*d)+1] -= s
print(ans)

Solution (Python):
from collections import deque
N, D, A = map(int, input().split())

ys = []
hs = []
for i in range(N):
    X, H = map(int, input().split())
    ys.append((X,i))
    hs.append(-(-H//A))

ys = sorted(ys, key=lambda x : x[0])
l = ys[0][0] + 2*D
li = 0
dmg = 0
r = 0
for y, i in ys:
    while (not l >= y):
        li += 1
        l = ys[li][0] + 2*D
        dmg -= hs[ys[li-1][1]]
    tr = max(0, hs[i]-dmg)
    hs[i] = tr
    dmg += tr
    r += tr
print(r)

Solution (Python):
from collections import deque

def main():
    N, D, A = list(map(int, input().split()))
    XH = []
    for _ in range(N):
        x, h = map(int, input().split())
        h = (h + A - 1) // A
        XH.append((x, h))
    XH.sort()
    D *= 2
    Q = deque()
    x0, h0 = XH[0]
    Q.append((x0 + D, h0))
    r = h0
    c = h0
    for x, h in XH:
        while Q and Q[0][0] < x:
            _, hh = Q.popleft()
            c -= hh
        h -= c
        if h > 0:
            Q.append((x + D, h))
            c += h
            r += h
    print(r)

main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, D, A, XH):
    XH.sort()
    X = [x for x, _ in XH]
    H = [h for _, h in XH]

    q = deque()
    ans = 0
    dmg = 0
    for i in range(N):
        while q and q[0][0] < X[i]:
            _, d = q.popleft()
            dmg -= d
        if H[i] <= dmg:
            continue
        ans += -(-(H[i] - dmg) // A)
        q.append((X[i]+2*D, (-(-(H[i] - dmg) // A))*A))
        dmg += (-(-(H[i] - dmg) // A))*A
    return ans


def main():
    N, D, A = read_int_n()
    XH = [read_int_n() for _ in range(N)]
    print(slv(N, D, A, XH))


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_right

N, D, A = map(int, input().split())
M = []
for i in range(N):
  x, h = map(int, input().split())
  M.append((x, -(-h//A)))
M.sort(key=lambda x: x[0])
X = list(map(lambda x: x[0], M))
H = list(map(lambda x: x[1], M))

dmg = [0] * (N+1)
ans = 0

for i in range(N):
  x, h = M[i]
  h = max(0, h - dmg[i])
  dmg[bisect_right(X, x + 2*D)] -= h
  dmg[i+1] += dmg[i] + h
  ans += h
print(ans)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys


mod = 10**9+7
sys.setrecursionlimit(mod) 

def LI(): return list(map(int, sys.stdin.readline().split()))

N, D, A = LI()
xh = []

for i in range(N):
    xh.append(LI())
xh.sort()
X = []
for i in range(N):
    X.append(xh[i][0])

bomb = [0 for i in range(N)]
ans = 0
now_dm = 0
for i in range(N):
    x,H = xh[i]
    now_dm += bomb[i]
    if now_dm >= H:
        pass
    else:
        ans += math.ceil((H - now_dm)/A)
        dm = math.ceil((H-now_dm)/A) * A
        ind = bisect.bisect_right(X, x+2*D)
        if i + 1 < N:
            bomb[i+1] += dm
        if ind < N:
            bomb[ind] -= dm

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

class DualSegmentTree:
    def __init__(self, n) :
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [0] * (self.N0*2)

    def update(self, l, r, val) :
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1:
                self.data[l] = self.data[l] + val
                l += 1
            if r & 1:
                self.data[r-1] = self.data[r-1] + val
                r -= 1
            l //= 2
            r //= 2

    def query(self, i):
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0:
            i //= 2
            ret = ret + self.data[i]
        return ret




def main():
    N,D,A = list(map(int,input().split()))

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

    enemy.sort(key=lambda x:x[0])
    def bisect(index):
        x = enemy[index][0]
        if enemy[N-1][0] <= x + 2*D:
            return N-1
        l = index
        r = N-1
        while r-l>1:
            if enemy[(r+l)//2][0] <= x + 2*D:
                l = (r+l)//2
            else:
                r = (r+l)//2
        return l
    ST = DualSegmentTree(N)

    for i in range(N):
        ST.update(i,i+1,enemy[i][1])

    count = 0
    for i in range(N):
        v = ST.query(i)
        if v>0:
            count += v
            j = bisect(i)
            ST.update(i,j+1,-v) 

    print(count)

if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_right

N, D, A = map(int, input().split())
M = []
for i in range(N):
  x, h = map(int, input().split())
  M.append((x, -(-h//A)))
M.sort(key=lambda x: x[0])
X = list(map(lambda x: x[0], M))
H = list(map(lambda x: x[1], M))

dmg = [0] * (N+1)
ans = 0

for i in range(N):
  x, h = M[i]
  h = max(0, h - dmg[i])
  dmg[i] += h
  dmg[bisect_right(X, x + 2*D)] -= h
  dmg[i+1] += dmg[i]
  ans += h
print(ans)

Solution (Python):
import bisect
import math
import sys
input=sys.stdin.readline
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
g=[0]*n
cnt=0
for i in range(n):
    if h[i]>0:
        m=math.ceil(h[i]/a)
        cnt+=m
        k=bisect.bisect_right(x,x[i]+2*d,lo=i)
        if i!=n-1:
            g[i]-=m*a
            if k<n:
                g[k]+=m*a
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
    else:
        if i!=n-1:
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
print(cnt)

Solution (Python):
import math
N, D, A = map(int, input().split())

M = []
for i in range(N):
    X, H = map(int, input().split())
    M.append((X, H))
M.sort(key=lambda x: x[0])

d = []
i = 0

ans = 0
B = 0
for X, H in M:
    while i != len(d) and X > d[i][0]:
        B -= d[i][1]
        i += 1
    if H > B:
        t = math.ceil((H-B)/A)
        ans += t
        B += t*A
        d.append((X+2*D, t*A))


print(ans)

Solution (Python):
import bisect
import math
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
g=[0]*n
cnt=0
for i in range(n):
    
    if h[i]>0:
        m=math.ceil(h[i]/a)
        cnt+=m
        k=bisect.bisect_right(x,x[i]+2*d,lo=i)
        if i!=n-1:
            h[i]-=m*a
            g[i]-=m*a
            if k<n:
                g[k]+=m*a
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
    else:
        if i!=n-1:
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
print(cnt)

Solution (Python):
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for _ in range(n)]
xh.sort()

import collections
pq=collections.deque()

ans = 0
totalDamage = 0


for i in range(n):
    x,h = xh[i]
    while len(pq) > 0 and pq[0][0] < x:
        totalDamage -= pq[0][1]
        pq.popleft()
    h -=totalDamage
    if h <= 0:
        continue
    num = (h + a -1) //a
    ans += num
    dam = num*a
    totalDamage += dam
    pq.append((x+2*d,dam))

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x << 30) + h)
X = sorted(X)[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1] >> 30 <= Q[0][0]:
        xh = X.pop()
        x, h = xh >> 30, xh % (1<<30)
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
from operator import itemgetter

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X, key = itemgetter(0))[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X, key = lambda x: x[0])[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Solution (Python):
from heapq import heapify, heappush, heappop
from math import ceil

REAL = 0
UNREAL = 1

n, d, a = map(int, input().split())
xh = [list(map(int, input().split())) for _ in range(n)]

hp = []
for x, h in xh:
    heappush(hp, [x, REAL, h])

bomb_acm = 0
ans = 0
while hp:
    x, r, h = heappop(hp)
    if r == REAL:
        if h > bomb_acm:
            left = h - bomb_acm
            bomb_cnt = ceil(left / a)
            hp_dis = a * bomb_cnt
            bomb_acm += hp_dis
            heappush(hp, [x + 2 * d, UNREAL, hp_dis])
            ans += bomb_cnt

    else: 
        bomb_acm -= h

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X)[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Solution (Python):


import sys
input = sys.stdin.readline
from math import ceil
from collections import deque
N,D,A = map(int, input().split())
XH = [list(map(int,input().split())) for _ in range(N)]
XH.sort(key = lambda x:x[0])

q = deque()
d = 0
ans = 0

for x,h in XH:
    while q and q[0][0] < x:    
        d -= q.popleft()[1]
    h -= d
    if h > 0:
        num = ceil(h/A)
        ans += num
        q.append((x+2*D, num*A))    
        d += num*A
print(ans)

Solution (Python):
from collections import deque
import math
n, d, a = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))
data.sort()
dam = 0
ans = 0
q = deque()
for i in range(n):
    x,h = data[i]
    while q:
        k = q.popleft()
        if k[1] >= x:
            q.appendleft(k)
            break
        else:
            dam -= k[0]
    h -= dam
    h = max(h, 0)
    count = math.ceil(h / a)
    dam += count * a
    q.append([count * a, x + 2*d])
    ans += count
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
from operator import itemgetter

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X, key = itemgetter(0))[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
from operator import itemgetter
key = itemgetter(0)

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X)[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Solution (Python):
import math
from collections import deque

def main():
        
    N,D,A = map(int, input().split())

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

    xh.sort()

    ans = 0
    q = deque()
    dmg = 0
    for i in range(N):
        
        while q and q[0][0] < xh[i][0]:
            _, d = q.popleft()
            dmg -= d

        
        if xh[i][1] - dmg <= 0:
            continue

        remaining = xh[i][1] - dmg

        cnt = math.ceil(remaining / A)
        ans += cnt
        dmg += cnt * A
        
        q.append((xh[i][0] + 2*D, cnt*A))


    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
Xmax = 10**10
N, D, A = inpl()
XH = [inpl() for _ in range(N)]
XH.sort()
XH.append([Xmax,0])
ans = 0
d = 0
i = j = 0
R = []
while True:
    if j >= len(R) or XH[i][0] <= R[j][0]:
        x, h = XH[i]
        i += 1
        if x >= Xmax:
            break
        h -= d
        if h <= 0:
            continue
        else:
            k = (h-1)//A + 1
            R.append((x+2*D, k*A))
            d += k*A
            ans += k
    else:
        x, h = R[j]
        j += 1
        d -= h
print(ans)

Solution (Python):
import sys
n, D, a = map(int, input().split())
tg = []
for _ in range(n):
    x, h = map(int, sys.stdin.readline().split())
    c = h // a
    if h % a > 0:
        c+=1
    tg.append([x, c])

class BIT:
    def __init__(self, n):
        self.n = n
        self.N = 1 << n.bit_length()
        self.data = [0] * (self.N +1)

    def add(self, i, x):
        while i <= self.N:
            self.data[i] += x
            i += i & -i

    def sum(self, i):
        total = 0
        while i > 0:
            total += self.data[i]
            i -= i&-i
        return total

    def search(self, w):
        if w <= 0:
            return 0
        x = 0
        k = self.N >> 1
        while k > 0:
            if x+k <= self.N and self.data[x+k] < w:
                w -= self.data[x+k]
                x += k
            k = k >> 1
        return x+1

    def len(self):
        return self.data[self.N]

tg = sorted(tg, key=lambda x:x[0])
bit = BIT(n+2)
result = 0
ind = 0
for i in range(n):
    c = tg[i][1] - bit.sum(i+1)
    d = tg[i][0]
    if c <= 0:
        continue
    result += c
    wd = d + 2*D
    if ind < i:
        ind = i
    for j in range(ind, n):
        if tg[j][0] <= wd:
            ind = j
        else:
            break
    bit.add(i+1, c)
    bit.add(ind+2, -c)
print(result)

Solution (Python):
from sys import stdout
from collections import deque
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,d,a = inm()
xh = []
for i in range(n):
    xx,hh = inm()
    xh.append((xx,(hh+a-1)//a))
xh.sort()
cnt = 0
q = deque([])
ad = 0
for i in range(n):
    h = xh[i][1]
    x = xh[i][0]
    while len(q)>0 and q[0][0]<x:
        z = q.popleft()
        ad -= z[1]
    h -= ad
    if h<=0:
        continue
    cnt += h
    ad += h
    q.append((x+2*d,h))
print(cnt)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X, key = lambda x: x[0])[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Solution (Python):
N,D,A = map(int,input().split())
X = []
for _ in range(N):
    x,h = map(int,input().split())
    X.append([x,h])
X.sort()
if X[-1][0] - X[0][0] < 2 * D:
    ans = 0 
    max = 0
    for i in range(N):
        if X[i][1] > max:
            max = X[i][1]
    if max % A == 0:
        ans = max // A
    else:
        ans = max // A + 1
else:
    ans = 0
    for i in range(N):
        h = int(X[i][1])
        if h != 0:
            x = int(X[i][0])
            if h % A == 0:
                count = h // A
            else:
                count = h // A + 1
            ans += count
            dmg = A * count
    
            for j in range(i+1,N):
                x2 = int(X[j][0])
                h2 = int(X[j][1])
                if  x + (2 * D) < x2:
                    break
                else:
                    X[j][1] = max(0,h2-dmg)
                    
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


class BinaryIndexedTree:
    
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
    

def solve():
    n, d, a = LI()
    xh = LIR(n)
    xh.sort()
    ans = 0
    ldi = 0
    rdi = 0
    bit = BinaryIndexedTree(n+1)
    for i in range(n):
        x, h = xh[i]
        h -= bit.sum(i)
        if h > 0:
            t = (h - 1) // a + 1
            for rdi in range(rdi, n):
                if x + 2 * d < xh[rdi][0]:
                    rdi -= 1
                    break
            ans += t
            bit.add(rdi + 1, -t * a)
            bit.add(i, t * a)

    print(ans)

    return



if __name__ == '__main__':
    solve()

Solution (Python):
import math
n,d,a=map(int,input().split())
XH=[[int(i)for i in input().split()] for _ in range(n)]
XH.sort(key=lambda x:x[0])
ans=0
l=0
before=0
T=[0]*n
for i,xh in enumerate(XH):
    x,h=xh
    while XH[l][0]+2*d<x:
        before-=T[l]
        l+=1
    h-=before*a
    if h<=0:
        continue
    T[i]=math.ceil(h/a)
    ans+=T[i]
    before+=T[i]
print(ans)

Solution (Python):
import bisect
import sys
input = sys.stdin.readline
from collections import defaultdict
class Bit:
  def __init__(self, n):
    self.size = n
    self.tree = [0] * (n + 1)

  def sum(self, i):
    s = 0
    while i > 0:
        s += self.tree[i]
        i -= i & -i
    return s

  def add(self, i, x):
    while i <= self.size:
      self.tree[i] += x
      i += i & -i
n,d,a = map(int,input().split())
xh = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  xh[i][1] = (xh[i][1]+a-1)//a
xh.sort()
x = [xh[i][0] for i in range(n)]
remain = [xh[i][1] for i in range(n)]
ans = 0
bit = Bit(n+1)

for i in range(n):
  if bit.sum(i+1) >= remain[i]:
    continue
  br = bisect.bisect_right(x,x[i]+2*d)
  y = remain[i]-bit.sum(i+1)
  ans += y
  bit.add(i+1,y)
  bit.add(br+1,-y)
print(ans)

Solution (Python):
from bisect import bisect_right


def solve(n, d, a, xh_list):
    res = 0
    xh_list_s = sorted(xh_list, key=lambda x: x[0])
    x_list_s = [xh[0] for xh in xh_list_s]
    h_list_s = [xh[1] for xh in xh_list_s]
    dmg = 0
    wait_list = [0] * (n + 1)
    for i in range(n):
        dmg -= wait_list[i]
        v = h_list_s[i] - dmg
        if v > 0:
            t = (v - 1) // a + 1
            res += t
            dmg += t * a
            j = bisect_right(x_list_s, x_list_s[i] + 2 * d)
            wait_list[j] += t * a

    return res


def main():
    n, d, a = map(int, input().split())
    xh_list = []
    for _ in range(n):
        x, h = map(int, input().split())
        xh_list.append((x, h))
    res = solve(n, d, a, xh_list)
    print(res)


def test():
    assert solve(3, 3, 2, [(1, 2), (5, 4), (9, 2)]) == 2
    assert solve(9, 4, 1, [(1, 5), (2, 4), (3, 3), (4, 2), (5, 1), (6, 2), (7, 3), (8, 4), (9, 5)]) == 5
    assert solve(3, 0, 1, [(300000000, 1000000000), (100000000, 1000000000), (200000000, 1000000000)]) == 3000000000


if __name__ == "__main__":
    test()
    main()

Solution (Python):
import sys
N,D,A=[int(i) for i in input().split(" ")]
enemies=[]
for i in range(N):
    X,H=[int(j) for j in input().split(" ")]
    enemies.append([X,H])

enemies=sorted(enemies,key=lambda w:w[0])

if enemies[-1][0]-enemies[0][0]<=2*D:
    hpmax=sorted(enemies,key=lambda  w:w[1])[-1][1]
    if hpmax%A==0:
        print(hpmax//A)
    else:
        print(hpmax//A+1)
    sys.exit()


retval=0
for i in range(N):
    hp=enemies[i][1]
    place=enemies[i][0]
    if hp<=0:
        continue
    if hp%A==0:
        bomb=hp//A
    else:
        bomb=hp//A+1
    retval+=bomb

    for j in range(i,N):
        if enemies[j][0]-place>2*D:
            break
        enemies[j][1]-=bomb*A



print(retval)

Solution (Python):
import sys
input=sys.stdin.readline
import collections
n,d,a=map(int,input().split())
XH=[]
for i in range(n):
  XH.append([int(i) for i in input().split()])
XH.sort(key=lambda x:x[0])
D=collections.deque()
x,h=XH[0]
t=(h-1)//a+1
ans=t
D.append([x,h,t])
adj=t
for i in range(1,n):
  x,h=XH[i]
  while D:
    lx,lh,t=D.popleft()
    if lx<x-2*d:
      adj-=t
    else:
      D.appendleft([lx,lh,t])
      break
  h=max(0,h-adj*a)
  t=(h-1)//a+1
  ans+=t
  adj+=t
  D.append([x,h,t])
print(ans)

Solution (Python):
import collections
import bisect
import sys
input = sys.stdin.readline




n, d, a = [ int(v) for v in input().split() ]
monster = []
for _ in range(n):
    x, h = [ int(v) for v in input().split() ]
    monster.append([x, h])
monster.sort()


monster_x, monster_h = [], []
for x, h in monster:
    monster_x.append(x)
    monster_h.append(h)
    

deq = collections.deque([])
totaldamage = 0
ans = 0

for i in range(n):
    
    stop = 1
    while stop == 1 and len(deq) > 0:
        if deq[-1][0] < monster_x[i]:
            totaldamage -= deq[-1][1]
            deq.pop()
        else:
            stop = 0
    
    monster_h[i] -= totaldamage
    if monster_h[i] > 0:
        index = monster_x[i] + 2*d
        
        f = (monster_h[i] + a - 1) // a
        ans += f 
        totaldamage += f * a
        deq.appendleft([index, f*a])
        monster_h[i] = 0

print(ans)