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

from functools import cmp_to_key
import math
import bisect

n = int(input())
s = input()
k = 1
rank = [0] * (n+1)
tmp = [0] * (n+1)
sa = [''] * (n+1)

def compare_sa(i,j):
	if rank[i] != rank[j]:
		return -1 if rank[i] < rank[j] else 1
	else:
		if i + k <= n:
			ri = rank[i+k]
		else:
			ri = -1
		if j + k <= n:
			rj = rank[j+k]
		else:
			rj = -1
		return -1 if ri < rj else 1


for i in range(n+1):
	sa[i] = i
	if i < n:
		rank[i] = ord(s[i])
	else:
		rank[i] = -1

while k <= n:

	sa = sorted(sa,key=cmp_to_key(compare_sa))

	tmp[sa[0]] = 0

	for i in range(1,n+1):
		if compare_sa(sa[i-1],sa[i]) == -1:
			tmp[sa[i]] = tmp[sa[i-1]] + 1
		else:
			tmp[sa[i]] = tmp[sa[i-1]]

	for i in range(n+1):
		rank[i] = tmp[i]

	k *= 2

#saはインデックス、sorted_listは実際の文字列
sorted_list = []
for i in range(n+1):
	sorted_list.append(s[sa[i]:])
#print(sa)
#print(sorted_list)

#文字列検索
"""
T = ['ab','abra','abc','abracadabra','abracadabraaa','brabra','bra']
for t in T:
	start = bisect.bisect_left(sorted_list,t)
	end = bisect.bisect_left(sorted_list,t[:-1]+chr(ord(t[-1])+1))
	if start == end:
		print(t+'は存在しません')
	else:
		print(t+'は存在します')
"""

#lcp配列の作成
def getLCP(i,j):
	h = 0
	while i+h < n and j+h < n:
		if s[j+h] != s[i+h]:
			break
		h+=1
	return h

#lcp配列の最大値=最長の共通部分文字列のインデックス
#ans = sorted_list[ lcp.index(max(lcp)) ]
#ans = ans[:max(lcp)]
#print(ans)

ans = 0
for i in range(0,n):
	for j in range(i+1,n):
		lcp = min(getLCP(i,j),j-i)
		ans = max(ans,lcp)

print(ans)

### FIXED CODE ###

n = int(input())
s = input()

def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
        	j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A
ans = 0
for i in range(n-1):
	tmp = z_algo(s[i:])
	for j,zj in enumerate(tmp):
		if j+1 > zj:
			ans = max(ans,zj)

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

N, M = map(int, input().split())
MOD = 10 ** 9 + 7


factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, N + M + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if not (0 <= r <= n):
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


def nPr(n, r):
    if not (0 <= r <= n):
        return 0
    return nCr(n, r) * factorial[r] % MOD


ans = pow(nCr(M, N) * factorial[N], 2, MOD)
for r in range(1, N + 1):
    p = nCr(M, r) * pow(nCr(M - r, N - r), 2, MOD) * nCr(N, r) * factorial[r] * factorial[N - r] * factorial[N - r] % MOD
    p *= ((-1) ** ((r % 2) ^ 1))
    ans -= p
    ans %= MOD

print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
MOD = 10 ** 9 + 7


factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, N + M + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if not (0 <= r <= n):
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


def nPr(n, r):
    if not (0 <= r <= n):
        return 0
    return nCr(n, r) * factorial[r] % MOD


ans = pow(nCr(M, N) * factorial[N], 2, MOD)
for r in range(1, N + 1):
    p = nCr(M, r) * pow(nCr(M - r, N - r), 2, MOD) * nCr(N, r) * factorial[r] * factorial[N - r] * factorial[N - r] % MOD
    p *= ((-1) ** ((r % 2) ^ 1))
    ans -= p
    ans %= MOD

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

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

ans = 0
for i in range(min(A), max(A)+1):
    ans = max(A.count(i-1) + A.count(i) + A.count(i+1), ans)

print(ans)

### FIXED CODE ###

import collections

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

c = collections.Counter(A)
ans = 0
for i in range(min(A), max(A)+1):
    ans = max(c[i-1] + c[i] + c[i+1], ans)

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

n = int(input())
a = [int(input()) for _ in range(n)]
pos = 1
cnt = 0
passed = []
TF = True
while TF:
  pos -= 1
  if a[pos] in passed:
    TF = False
    print(-1)
  elif a[pos] == 2:
    print(cnt+1)
    TF = False
  else:
    passed.append(a[pos])
    pos = a[pos]
    cnt += 1

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
pos = 1
cnt = 0
passed = [0]*(n+1)
TF = True
while TF:
  pos -= 1
  temp = a[pos]
  if passed[temp] == 1:
    TF = False
    print(-1)
  elif temp == 2:
    print(cnt+1)
    TF = False
  else:
    passed[temp] = 1
    pos = temp
    cnt += 1
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
for i in range(K):
  LR.append([int(i) for i in input().split()])
for i in range(N):
  for lr in LR:
    if lr[0] <= i and i <= lr[1]:
      S.append(i)
S = list(set(S))
#print(S)

for i in range(1,N):
  if i in S:
    dp[i] = 1
  for j in range(len(S)):
    if i-S[j] < 1:
      break
    #print(i, S[j], i-S[j])
    dp[i] += 1*dp[i-S[j]]
    dp[i] %= mod

print(dp[-2])


### FIXED CODE ###

N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
dps = [0]*(N+1)
dps[1] = 1
dp[1] = 1
for i in range(K):
  LR.append([int(i) for i in input().split()])

for i in range(1,N+1):
  for l,r in LR:
    l,r = i - r,i - l
    #print(l,r)
    if r < 1:
      continue
    l = max(1,l)
    dp[i] += dps[r] - dps[l-1]
    dp[i] %= mod
    #print(dp[i])
    
  dps[i] = dps[i-1] + dp[i]
  #print(dp, dps)
print(dp[-1])
### BUGGY CODE ###

from sys import stdin

def main():

    input = stdin.readline

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

    for i in range(1,N+1):
        print(A.count(i))


if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin

def main():

    input = stdin.readline

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

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

    for i in ans:
        print(i)

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

N = int(input())
Y = []
c = 0
for i in range(N):
    S = input()
    if S not in Y:
        Y.append(S)
        c += 1
print(c)

### FIXED CODE ###

N = int(input())
Y = []
for i in range(N):
    Y.append(input())
print(len(set(Y)))
### BUGGY CODE ###

n = int(input())
ls = [int(x) for x in input().split()]
if 0 in ls:
    print(0)
    exit()
res = 1
for x in ls:
    res *= x
print(res if res <= 1000000000000000000 else -1)

### FIXED CODE ###

n = int(input())
ls = [int(x) for x in input().split()]
if 0 in ls:
    print(0)
    exit()
res = 1
for x in ls:
    if res <= 1000000000000000000:
        res *= x
    else:
        break

print(res if res <= 1000000000000000000 else -1)
### BUGGY CODE ###

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

a=0
i=-1
j=0
while True:
  i+=1
  if A.count(A[i])>=2:
    print("NO")
    a=1
    break
  else:
    A.remove(A[i])
    j+=1
    i-=1
    if j==N:
      break

if a==0:
  print("YES")

### FIXED CODE ###

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

if len(A) == len(set(A)):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()
    s_list = [str(c) for c in S]
    q_list = [list(map(int, input().split())) for i in range(Q)]

    ac_list = list()
    # get AC start point
    for i, n in enumerate(s_list):
        if n == "A" and i != (len(s_list) - 1):
            if s_list[i + 1] == "C":
                ac_list.append(i + 1)

    # answer Q
    for qs in q_list:
        counter = 0
        for start in ac_list:
            if qs[0] <= start and start < qs[1]:
                counter += 1
        print(counter)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()
    s_list = [str(c) for c in S]
    q_list = [list(map(int, input().split())) for i in range(Q)]

    ac_list = list()
    # get AC start point
    for i, n in enumerate(s_list):
        if n == "A" and i != (len(s_list) - 1):
            if s_list[i + 1] == "C":
                ac_list.append(i + 1)

    # set list
    temp = list()
    pre = 0
    counter = 0
    for s in ac_list:
        for i in range(pre, s):
            temp.append(counter)
        pre = s
        counter += 1

    for i in range(pre, N):
        temp.append(counter)

    # answer Q
    for qs in q_list:
        print(temp[qs[1] - 1] - temp[qs[0] - 1])


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

#!/usr/bin/env python
# coding: utf-8

# In[10]:


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

for i in range(N):
    tmp = [x for x in A]
    del tmp[i]
    print(max(tmp))


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[1]:


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


# In[6]:


idx_max = A.index(max(A))
tmp = [x for x in A]
del tmp[idx_max]
most_max = max(A)
second_max = max(tmp)
for i in range(N):
    if i == idx_max:
        print(second_max)
    else:
        print(most_max)


# In[ ]:
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

n,k=map(int,input().split())
m=10**9+7
to=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1, input().split())
  to[a].append(b)
  to[b].append(a)
frac=[1]*(10**5+1)
for i in range(1,10**5+1):
  frac[i]=frac[i-1]*i
  frac[i]%=m


def nPk(_n,_k):
  if _n<0 or _k<0 or _n-_k<0: return 0;
  a=frac[_n]
  b=frac[_n-_k]
  return (a*pow(b,m-2,m))%m


def dfs(_v, _u=-1):
  global ans
  for u in to[_v]:
    if u==_u: continue
    dfs(u, _v)
  p=len(to[_v])
  ans*=nPk(k,p+1) if _v==0 else nPk(k-2,p-1)
  ans%=m
    
    
ans=1
chk=[False]*n
dfs(0)
  
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

n,k=map(int,input().split())
m=10**9+7
to=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1, input().split())
  to[a].append(b)
  to[b].append(a)
frac=[1]*(10**5+1)
for i in range(1,10**5+1):
  frac[i]=frac[i-1]*i
  frac[i]%=m


def nPk(_n,_k):
  if _n<0 or _k<0 or _n-_k<0: return 0;
  a=frac[_n]
  b=frac[_n-_k]
  return (a*pow(b,m-2,m))%m


def dfs(_v, _u=-1):
  global ans
  for u in to[_v]:
    if u==_u: continue
    dfs(u, _v)
  p=len(to[_v])
  ans*=nPk(k,p+1) if _v==0 else nPk(k-2,p-1)
  ans%=m
    
    
ans=1
chk=[False]*n
dfs(0)
  
print(ans)
### BUGGY CODE ###

import math


class Sieve:
    """Sieve of Eratosthenes.

    List primes up to n.
    """

    def __init__(self, n):
        self.__prime = []
        self.__is_prime = [i >= 2 for i in range(n + 1)]

        for i in range(2, int(math.sqrt(n)) + 1):
            if self.__is_prime[i]:
                for j in range(i * i, n + 1, i):
                    self.__is_prime[j] = False

        for i in range(2, n + 1):
            if self.__is_prime[i]:
                self.__prime.append(i)

    def prime(self):
        return self.__prime

    def is_prime(self, n):
        return self.__is_prime[n]


if __name__ == '__main__':
    N = int(input())  # 2 <= N <= 3000
    a = list(map(int, input().split()))  # 2 <= ai <= 100000
    b = [ai for ai in a]

    p = Sieve(100000).prime()  # len = 9952

    prime_to_power = [0 for _ in range(p[-1] + 1)]
    for i in range(len(a)):
        for prime in p:
            power = 0
            while b[i] % prime == 0:
                b[i] /= prime
                power += 1
            prime_to_power[prime] = max(prime_to_power[prime], power)
            if b[i] == 1:
                break

    lcm = 1
    for i in range(len(prime_to_power)):
        lcm *= i ** prime_to_power[i]
    m = lcm - 1
    ans = 0
    for ai in a:
        ans += m % ai
    print(ans)


### FIXED CODE ###

import math


class Sieve:
    """Sieve of Eratosthenes.

    List primes up to n.
    """

    def __init__(self, n):
        self.__prime = []
        self.__is_prime = [i >= 2 for i in range(n + 1)]

        for i in range(2, int(math.sqrt(n)) + 1):
            if self.__is_prime[i]:
                for j in range(i * i, n + 1, i):
                    self.__is_prime[j] = False

        for i in range(2, n + 1):
            if self.__is_prime[i]:
                self.__prime.append(i)

    def prime(self):
        return self.__prime

    def is_prime(self, n):
        return self.__is_prime[n]


def bf(N, a):
    p = Sieve(max(a) + 1).prime()  # len <= 9952

    prime_to_power = {}
    for prime in p:
        prime_to_power[prime] = 0

    for i in range(N):
        ai = a[i]
        for prime in p:
            power = 0
            while ai % prime == 0:
                ai //= prime
                power += 1
            prime_to_power[prime] = max(prime_to_power[prime], power)
    lcm = 1
    for prime in prime_to_power:
        lcm *= prime ** prime_to_power[prime]
    m = lcm - 1
    ans = 0
    for ai in a:
        ans += m % ai
    return ans


def al(N, a):
    return sum(a) - len(a)


if __name__ == '__main__':
    N = int(input())  # 2 <= N <= 3000
    a = list(map(int, input().split()))  # 2 <= ai <= 100000
    # print(bf(N, a))
    print(al(N, a))
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()

    y = [0] * (10**6 + 1)
    for i in range(N):
        y[A[i]] += 1

    ans = 0
    for i in range(N):
        x = A[i]
        if x > 1:
            if y[1] : continue
        if y[x] > 1: continue

        f = 1
        for j in range(2,int(math.sqrt(x))+1):
            if x % j == 0 and (y[j] or y[x//j]):
                f = 0
                break
        ans += f

    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    y = [0] * (10**6 + 1)
    z = [0] * (10**6 + 1)
    A = []
    for x in sys.stdin.readline().split():
        x = int(x)
        A.append(x)
        y[x] += 1
        if y[x] == 1:
            c = x * 2
            while c <= 10**6:
                z[c] = 1
                c += x

    ans = 0
    for i in range(N):
        x = A[i]
        if y[x] > 1: continue

        if z[x] == 0:
            ans += 1

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

l, r = map( int, input().split())

amr = []
for x in range(l,r+1):
    amr.append(x%2019)
# print(amr)
amr = list(set(amr))
ij_mod = []
for i in range(len(amr)-1):
    for j in range(i+1,len(amr)):
        ij_mod.append((amr[i]*amr[j])%2019)
print(min(ij_mod))




### FIXED CODE ###

l, r = map( int, input().split())

amr = []
for x in range(l,r+1):
    if len(amr) >= 2019:
        break
    amr.append(x%2019)
# print(amr)
amr = list(set(amr))
ij_mod = []
for i in range(len(amr)-1):
    for j in range(i+1,len(amr)):
        ij_mod.append((amr[i]*amr[j])%2019)
print(min(ij_mod))
### BUGGY CODE ###

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

sum=0

for i in range(len(num)):
  for j in num[i+1:]:
    sum += (num[i] * j % (10**9+7))
    sum = sum % (10**9+7)
    
print(sum)

### FIXED CODE ###

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

tot = 0
num2 = [0]*(N-1)
numtot = sum(num)

for i in range(len(num)-1):
  numtot -= num[i]
  num2[i] = numtot % (10**9+7)
  
  num1 = num[i] % (10**9+7)
  
  tot += num1 * num2[i]
  
  if tot >= (10**9+7): tot = tot % (10**9+7)

print(tot)
### BUGGY CODE ###

from math import sqrt
N = int(input())
ans = 0
# if N // i = p, N % i = p, 
# N = pi + p = p(i+1)
# p < sqrt(N) and p < i 
for p in range(1,N):
  if N % p > 0:
    continue
  i = N//p - 1
  if p >= i:
    break
  ans += i
    
print(ans)

### FIXED CODE ###

from math import sqrt
N = int(input())
ans = 0
# if N // i = p, N % i = p, 
# N = pi + p = p(i+1)
# p < sqrt(N) and p < i 
for p in range(1,N):
  if p > N/p - 1:
    break
  if N % p > 0:
    continue
  i = N//p - 1
  if p >= i:
    break
  ans += i
    
print(ans)
### BUGGY CODE ###

n = int(input())
a = []
wb = []
cnt = 0
num_before = 1
light = 1
for i in range(n):
    a.append(int(input()))
while light != 2:
    wb.append(light)
    light = a[num_before-1]
    num_before = light
    if light in wb:
        print(-1)
        break 
    cnt += 1
if light == 2:
    print(cnt)

### FIXED CODE ###

a = [int(input()) for i in range(int(input()))]
i = a[0]
cnt = 1
while(i != 2 and cnt <= 10**5):
    i = a[i-1]
    cnt += 1
if cnt <= 10**5:
    print(cnt)
else:
    print(-1)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
tmp = set()

while True:
    v = a[0]
    if v*2>a[-1]:
        for item in a:
            tmp.add(item)
    tmp.add(v)
    a = [item for item in a if item%v!=0]
    if not a:
        break

# tmp = [a[0]]
# for i in range(1, n):
#     num = a[i]
#     for i in range():
#         item = tmp[i]
#         if num%item==0:
#             break
#     else:
#         tmp.append(num)
tmp = set(tmp) - s
print(len(tmp))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
ok = set()
p = set(list(range(1, 10**6+1)))
ck = list(c.keys())
ck.sort()
for num in ck:
    if num in p:
        ok.add(num)
    i = 2
    while num*i<=10**6:
        if num*i in p:
            p.remove(num*i)
        i += 1
tmp = ok
tmp = set(tmp) - s
print(len(tmp))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]

count = 0
S = sum(a)
sub = glist(301,301,301)

for s in range(S+1):
    for i1 in range(s+1):
        for i2 in range((s-i1)//2+1):
            d,m = divmod((s-i1-2*i2), 3)
            if m:
                continue
            i3 = d
            count += 1
            if i1==i2==i3==0:
                sub[i1][i2][i3] = 0
                continue
            ans = 1
            p = 0
            if i1>0:
                ans += i1/n * sub[i1-1][i2][i3]
                p += i1/n
            if i2>0:
                ans += i2/n * sub[i1+1][i2-1][i3]
                p += i2/n
            if i3>0:
                ans += i3/n * sub[i1][i2+1][i3-1]
                p += i3/n
            ans = ans/p
            sub[i1][i2][i3] = ans
print(sub[n1][n2][n3])

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

from collections import Counter, defaultdict
c = Counter(a)
n1, n2, n3 = c[1], c[2], c[3]
n0 = c[0]
def glist(*l, fill=None):
    if len(l)==1:
        return [fill]*l[0]
    ll = l[1:]
    return [glist(*ll) for _ in range(l[0])]

count = 0
S = sum(a)
sub = glist(n1+n2+n3+1,n2+n3+1,n3+1)
sub[0][0][0] = 0
#     for i1 in range(min(n+1, s+1)):
#         for i2 in range(min(n+1, (s-i1)//2+1)):
for i3 in range(n3+1):
    for i2 in range(n2+n3+1-i3):
        for i1 in range(n1+n2+n3 - (i2+i3) + 1):
            if i1==i2==i3==0 or i1+i2+i3>n:
                continue
#             print(i1,i2,i3)
            ans = n
            p = 0
            if i1>0:
                ans += i1 * sub[i1-1][i2][i3]
                p += i1
            if i2>0:
                ans += i2 * sub[i1+1][i2-1][i3]
                p += i2
            if i3>0:
                ans += i3 * sub[i1][i2+1][i3-1]
                p += i3
            ans = ans/p
            sub[i1][i2][i3] = ans
print(sub[n1][n2][n3])
### BUGGY CODE ###

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

import numpy as np
from bisect import bisect_right

H=np.array(H)
ans=0
import math
for i in range(N):
  if np.all(H<=0):
    break
  if H[i]<=0:
    continue
  else:
    xj=2*D+X[i]
    j=bisect_right(X, xj)
    att=math.ceil(H[i]/A)
    H[i:j]-=A*att
    ans+=att
#print(H)
print(ans)

### FIXED CODE ###

N,D,A=map(int,input().split())
XH=[]
for _ in range(N):
  x,h=map(int,input().split())
  XH.append([x,h])
XH=sorted(XH, key=lambda x:x[0])
X=[XH[i][0] for i in range(N)]
H=[XH[i][1] for i in range(N)]
from math import ceil
from bisect import bisect_right
imos=[0]*(N+1)
hit=0
ans=0
for i in range(N):
  hit+=imos[i]
  restH=H[i]-hit*A
  if restH>0:
    ans+=ceil(restH/A)
    hit+=ceil(restH/A)
    ind=bisect_right(X,X[i]+2*D)
    imos[ind]-=ceil(restH/A)
print(ans)
### BUGGY CODE ###

import sys

import numpy as np

input = sys.stdin.readline


def solve():
    infinity = 10 ** 10
    n, m, le = map(int, input().split())
    paths = np.full((n, n), infinity)
    for i in range(n):
        paths[i,i] = 0

    for _ in range(m):
        a, b, c = map(int, input().split())
        paths[a - 1, b - 1] = c
        paths[b - 1, a - 1] = c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                paths[i, j] = min(paths[i, j], paths[i, k] + paths[k, j])

    refuels = np.array(paths, copy=True)
    for i in range(n):
        for j in range(n):
            refuels[i, j] = 1 if refuels[i, j] <= le else infinity
            if i == j:
                refuels[i, j] = 0

    for k in range(n):
        for i in range(n):
            for j in range(n):
                refuels[i, j] = min(refuels[i, j], refuels[i, k] + refuels[k, j])

    q = int(input())
    answer = []
    for _ in range(q):
        s, t = map(int, input().split())
        answer.append(refuels[s-1, t-1] - 1 if refuels[s-1, t-1] < infinity else -1)

    print("\n".join(map(str, answer)))


if __name__ == "__main__":
    solve()


### FIXED CODE ###


from scipy.sparse.csgraph import floyd_warshall
import numpy as np

N, M, L = map(int, input().split())
graph = np.full((N, N), 10 ** 10)
for _ in range(M):
    s, t, w = map(int, input().split())
    if w <= L:
        graph[s - 1][t - 1] = graph[t - 1][s - 1] = w
graph = floyd_warshall(graph, directed=False)
graph = floyd_warshall(graph <= L, directed=False)
graph[np.isinf(graph)] = 0

Q = int(input())
ans = []
for _ in range(Q):
    s, t = map(int, input().split())
    ans.append(int(graph[s - 1][t - 1]) - 1)
print(*ans, sep='\n')
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

for i in range(q):
    l, r = map(int, input().split())
    s_i = s[l-1:r]
    ans_i = "".join(s_i.split("AC"))
    print(
        (len(s_i) - len(ans_i)) // 2
    )

### FIXED CODE ###

import numpy as np
n, q = map(int, input().split())
s = input()
w = np.zeros(n, dtype=int)

a = 0
for i in range(n):
    if s[i] == "A":
        if a == 0:
            a += 1
    elif s[i] == "C":
        if a:
            w[i-1] = 1
            a -= 1
    else:
        if a:
            a -= 1

ans = np.append(np.zeros(1, dtype=int), np.cumsum(w))
for _ in range(q):
    l, r = map(int, input().split())
    print(ans[r-1] - ans[l-1])