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

s = input()
t = input()
len_s = len(s)

a = ord('a')
alph = [[] for _ in range(ord('z')-a+1)]
for i, c in enumerate(s):
  alph[ord(c)-a].append(i)

tmp = alph[ord(t[0])-a]
if tmp:
  idx = min(tmp)
  for c in t[1:]:
    tmp = alph[ord(c)-a]
    if tmp:
      position = idx % len_s
      delta = len_s
      for i in tmp:
        delta = min(delta, (i - idx - 1) % len_s + 1)
      idx += delta
    else:
      idx = -2
      break
  print(idx + 1)
else:
  print(-1)

### FIXED CODE ###

s = input()
t = input()
len_s = len(s)
a = ord('a')
dictionary = {chr(a + i): [[], 0] for i in range(26)}
for i in range(len_s):
  dictionary[s[i]][0].append(i)
  dictionary[s[i]][1] += 1
repeat = 0
cur_index = -1
for c in t:
  indices, len_indices = dictionary[c]
  if len_indices == 0:
    repeat = 0
    cur_index = -2
    break
  inf = -1
  sup = len_indices
  while sup - inf > 1:
    x = (inf + sup) // 2
    if indices[x] > cur_index:
      sup = x
    else:
      inf = x
  if sup == len_indices:
    repeat += 1
    cur_index = indices[0]
  else:
    cur_index = indices[sup]
print(len_s * repeat + cur_index + 1)
### BUGGY CODE ###

N, K = map(int, raw_input().split())

h = list(map(int, raw_input().split()))
dp = [10 ** 9 + 1] * N
dp[0] = 0
for i in range(N):
    for j in range(i + 1, i + K + 1):
        if j < N:
            dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))
print(dp[N - 1])

### FIXED CODE ###

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

h = list(map(int, input().split()))
dp = [10 ** 9 + 1] * N
dp[0] = 0
for i in range(N):
    for j in range(i + 1, i + K + 1):
        if j < N:
            dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))
        else:
            break
print(dp[N - 1])
### BUGGY CODE ###

S = input()
Q = int(input())

for _ in range(Q):
    q = input()
    if len(q) == 1:
        S = S[::-1]
    else:
        T, F, C = q.split()
        if int(F) == 1:
            S = C + S
        else:
            S = S + C

print(S)


### FIXED CODE ###

from collections import deque

S = list(input())
Q = int(input())

d = deque(S)
head = "l"

for _ in range(Q):
    q = input()
    if len(q) == 1:
        if head == "l":
            head = "r"
        else:
            head = "l"
    else:
        T, F, C = q.split()
        if int(F) == 1:
            if head == "l":
                d.appendleft(C)
            else:
                d.append(C)
        else:
            if head == "l":
                d.append(C)
            else:
                d.appendleft(C)
if head == "l":
    print("".join(list(d)))
else:
    print("".join(list(d)[::-1]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n, q = map(int, input().split())
edges = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

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


def dfs(v, parent):
    for v2 in edges[v]:
        if v2 == parent:
            continue
        count[v2] += count[v]
        dfs(v2, v)


dfs(0, None)
print(*count)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, q = map(int, input().split())
edges = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    edges[b].append(a)

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


def dfs(v, parent):
    for v2 in edges[v]:
        if v2 == parent:
            continue
        count[v2] += count[v]
        dfs(v2, v)


dfs(0, None)
print(*count)
### BUGGY CODE ###

#https://atcoder.jp/contests/abc134/tasks/abc134_d
import sys
input = sys.stdin.readline

n = int(int(input()))
a = [int(i) for i in input().split()]

b = [0] * n
for i in reversed(range(1, n + 1)):
    s = 0
    for j in range(1, n + 1):
        if j % i == 0 and j != i:
            s += a[j - 1]
    
    if s % 2 == a[i - 1]:
        b[i - 1] = 0
    else:
        b[i - 1] = 1
#print(b)
e = sum(b)
print(e)

if e != 0:
    d = []
    for i in range(n):
        if b[i] == 1:
            d.append(i + 1)
    print(' '.join(map(str, d)))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
arr = [0 for _ in range(n)]
for i in reversed(range(n)):
    s = 0
    for j in range(i, n, i+1):
        s += arr[j]
    s %= 2
    if a[i] != s:
        arr[i] = 1
print(sum(arr))
for i in range(n):
    if arr[i] == 1:
        print(i+1, end=' ')
print('')
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N = int(input())
S = list()
for i in range(N):
    S.append(input())

SS = sorted(list((set(S))))
count = list()
for ss in SS:
    count.append(S.count(ss))

m = max(count)
ans = list()
for i in range(len(count)):
    if count[i] == m:
        print(SS[i])


### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())
S = list()
for i in range(N):
    S.append(input())

S.sort()
count = list()
now = 0
for i in range(N - 1):
    if S[i] != S[i + 1]:
        count.append([now, i - now + 1])
        now = i + 1
    if i + 1 == N - 1:
        count.append([now, len(S) - now])

m = max([c[1] for c in count])
for c in count:
    if c[1] == m:
        print(S[c[0]])
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n = I()
    a = LI()
    b = LI()

    def f(a,b,n):
        c = sorted([(ai,bi) for ai,bi in zip(a,b) if ai < bi], reverse=True)
        a = [_[0] for _ in c]
        b = [_[1] for _ in c]
        if len(c) == 0:
            return n
        if len(c) == 1:
            return n % c[0][0] + n // c[0][0] * c[0][1]

        r = n
        for i in range(0,n+1,a[0]):
            t = i // a[0] * b[0] + f(a[1:], b[1:], n-i)
            if r < t:
                r = t
        return r

    t = f(a,b,n)
    r = f(b,a,t)

    return r


print(main())



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    n = I()
    a = LI()
    b = LI()

    def f(c,n):
        c0 = c[0]
        if len(c) == 1:
            return n % c0[0] + n // c0[0] * c0[1]

        r = n
        for i in range(0,n+1,c0[0]):
            t = i // c0[0] * c0[1] + f(c[1:], n-i)
            if r < t:
                r = t
        return r

    c = sorted([(ai,bi) for ai,bi in zip(a,b) if ai < bi], reverse=True)
    t = n
    if len(c) > 0:
        t = f(c,n)

    d = sorted([(ai,bi) for ai,bi in zip(b,a) if ai < bi], reverse=True)
    r = t
    if len(d) > 0:
        r = f(d,t)

    return r


print(main())
### BUGGY CODE ###

import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
l_c = len(C)
ans = 0
for a in A:
    i = bisect.bisect_right(B, a)
    for b in B[i:]:
        j = bisect.bisect_right(C, b)
        ans += l_c - j
print(ans)


### FIXED CODE ###

import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
l_c = len(C)
ans = 0
for b in B:
    n_a = bisect.bisect_left(A, b)
    n_c = l_c - bisect.bisect_right(C, b)
    ans += n_a*n_c
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
    
n,m,k=map(int,input().split())
pair=[-1]*n

def main():
#    n,m,k=map(int,input().split())
    g=[[] for i in range(n)]
    x=[[] for i in range(n)]
    a=[0]*m
    b=[0]*m
#    pair=[-1]*n
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
        a[i]=ai-1
        b[i]=bi-1
        unite(a[i],b[i])
    for i in range(k):
        ci,di=map(int,input().split())
        x[ci-1].append(di-1)
        x[di-1].append(ci-1)

    ii=0        
    ss=size(ii)-len(g[ii])-len(x[ii])-1
    strs=""
    for i in range(n):
        ss=size(i)-1
        rooti=root(i)
        for gi in g[i]:
            if root(gi)==rooti:
                ss-=1
        for xi in x[i]:
            if root(xi)==rooti:
                ss-=1
        strs=strs+" "+str(ss)
    print(strs[1:])
    
def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return False
    if pair[x]>pair[y]:
        x,y=y,x
    pair[x]+=pair[y]    
    pair[y]=x
    return True

def size(x):
    return -pair[root(x)]


main()
    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
#input = sys.stdin.readline
    
n,m,k=map(int,input().split())
pair=[-1]*n

def main():
#    n,m,k=map(int,input().split())
    g=[[] for i in range(n)]
    x=[[] for i in range(n)]
    a=[0]*m
    b=[0]*m
#    pair=[-1]*n
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
        a[i]=ai-1
        b[i]=bi-1
        unite(a[i],b[i])
    for i in range(k):
        ci,di=map(int,input().split())
        x[ci-1].append(di-1)
        x[di-1].append(ci-1)

#    strs=""
#    sss=[]
    for i in range(n):
        ss=size(i)-1
        rooti=root(i)
        for gi in g[i]:
            if root(gi)==rooti:
                ss-=1
        for xi in x[i]:
            if root(xi)==rooti:
                ss-=1
#        strs=strs+" "+str(ss)
#        sss.append(ss)
        print(ss,end=" ")
    print(" ")
    
def root(x):
    if pair[x]<0:
        return x
    else:
        tmp=root(pair[x])
        pair[x]=tmp
        return tmp

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y:return False
    if pair[x]>pair[y]:
        x,y=y,x
    pair[x]+=pair[y]    
    pair[y]=x
    return True

def size(x):
    return -pair[root(x)]


main()
### BUGGY CODE ###

n = int(input())
d = list(map(int,input().split()))
c = 0
k = 1
d.sort()

for i in range(1,max(d)+1):
  ab = [j for j in d if i <= j]
  ar = [j for j in d if i > j]
  #print(ab,ar)
  if(len(ab)==len(ar)):
    c = c + 1
  ab = 0
  ar = 0
print(c)

### FIXED CODE ###

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

d.sort()

print(d[int(n/2)] - d[int(n/2)-1])
### BUGGY CODE ###

n = int(input())
numbers = input()

lst = []
lst2 = []
lst3 = []
for i in range(n):
  pin = ''
  if numbers[i] not in lst:
    pin += numbers[i]
    lst.append(i)
    for j in range(i+1, n):
      pin += numbers[j]
      if pin not in lst2:
        lst2.append(pin)
        for k in range(j+1, n):
          pin += numbers[k]
          if pin not in lst3:
            lst3.append(pin)
          pin = pin[0] + pin[1]
      pin = pin[0]
print(len(lst3))

### FIXED CODE ###

n = int(input())
numbers = input()

lst = []
ans = []
for i in range(n):
  pin = ''
  if numbers[i] not in lst:
    pin += numbers[i]
    lst.append(pin)
    lst2 = []
    for j in range(i+1, n):
      pin += numbers[j]
      if pin[1] not in lst2:
        lst2.append(pin[1])
        lst3 = []
        for k in range(j+1, n):
          pin += numbers[k]
          if pin[2] not in lst3:
            lst3.append(pin[2])
            ans.append(pin)
          if ('0' in lst3) and ('1' in lst3) and ('2' in lst3) and ('3' in lst3) and ('4' in lst3) and ('5' in lst3) and ('6' in lst3) and ('7' in lst3) and ('8' in lst3) and ('9' in lst3):
            break
          pin = pin[0] + pin[1]
      if ('0' in lst2) and ('1' in lst2) and ('2' in lst2) and ('3' in lst2) and ('4' in lst2) and ('5' in lst2) and ('6' in lst2) and ('7' in lst2) and ('8' in lst2) and ('9' in lst2):
        break
      pin = pin[0]
    if ('0' in lst) and ('1' in lst) and ('2' in lst) and ('3' in lst) and ('4' in lst) and ('5' in lst) and ('6' in lst) and ('7' in lst) and ('8' in lst) and ('9' in lst):
      break
print(len(ans))
### BUGGY CODE ###

import sys
import heapq
from collections import deque

input = sys.stdin.readline

N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A = [-i for i in A]
B = [-i for i in B]
C = [-i for i in C]
BD = [i for i in B]


heapq.heapify(A)
heapq.heapify(B)
heapq.heapify(C)
heapq.heapify(BD)

ai = [0]*N
bi = [0]*N
ci = [1]*N

def compete_cal(N, B, C, bi, ci):
    for i in range(N):
        b=-heapq.heappop(B)
        ciq = deque(ci)
        while len(C)>0:
          c=-heapq.heappop(C)
          if c>b:
              bi[i]+=ciq.popleft()
          else:
              heapq.heappush(C, -c)

    for i in range(1,N):
        bi[i]+=bi[i-1]

    return bi   

bi = compete_cal(N, B, C, bi, ci)

ai = compete_cal(N, A, BD, ai, bi)
    
print(sum(ai))

### FIXED CODE ###

import sys
import heapq
from collections import deque

input = sys.stdin.readline

N = int(input())

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A = [-i for i in A]
B = [-i for i in B]
C = [-i for i in C]
BD = [i for i in B]


heapq.heapify(A)
heapq.heapify(B)
heapq.heapify(C)
heapq.heapify(BD)

ai = [0]*N
bi = [0]*N
ci = [1]*N


for i in range(N):
    b=-heapq.heappop(B)
    cnt=False
    while not cnt:
        if len(C)==0:
            cnt=True
            break
        else:
            c=-heapq.heappop(C)
            if c>b:
                bi[i]+=1
            else:
                cnt=True
                heapq.heappush(C, -c)

for i in range(1,N):
    bi[i]+=bi[i-1]

bi = deque(bi)   
    
for i in range(N):
    a=-heapq.heappop(A)
    while len(BD)>0:
        b=-heapq.heappop(BD)
        if b>a:
            ai[i]+=bi.popleft()
        else:
            heapq.heappush(BD, -b)
            break
        
         
for i in range(1,N):
    ai[i]+=ai[i-1]
    
print(sum(ai))
### BUGGY CODE ###

from functools import reduce
import itertools
def solve():
    N = int(input())
    primes = itertools.permutations(prime_factorize(N))

    min_sub = float('inf')
    for p in primes:
        p = [1] + list(p) + [1]
        for border in range(1, len(p)):
            a = reduce(lambda x, y: x*y, p[:border])
            b = reduce(lambda x, y: x*y, p[border:])
        
            if min_sub > a + b:
                min_sub = a + b 
    
    print(min_sub-2)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a                

if __name__ == '__main__':
    solve()


### FIXED CODE ###

import math
def solve():
    N = int(input())
    rootN = math.sqrt(N)

    min_val = float('inf')
    for a in range(1, math.floor(rootN) + 1):
        if N % a == 0:
            b = N / a
            min_val = min(min_val, a + b - 2)
    
    print(int(min_val))

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

n = int(input())
a = list(map(int, input().split()))
result = 1
for number in a:
    result *= number
if result > 10 ** 18:
    print(-1)
else:
    print(result)


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    result = 1
    if 0 in a:
        print(0)
        return
    for number in a:
        result *= number
        if result > 10 ** 18:
            print(-1)
            return
    print(result)

main()
### BUGGY CODE ###

# https://atcoder.jp/contests/abc158/tasks/abc158_d

S = input()
Q = int(input())

for _ in range(Q):
    query = input()
    if query[0] == '1':
        S = S[::-1]
    else:
        if query[2] == '1':
            S = query[4] + S
        else:
            S = S + query[4]

print(S)


### FIXED CODE ###

# https://atcoder.jp/contests/abc158/tasks/abc158_d
from collections import deque

S = input()
Q = int(input())

is_reverse = False
text = deque(S)
for _ in range(Q):
    query = input()
    if query[0] == '1':
        is_reverse = not is_reverse
    else:
        if query[2] == '1':
            if is_reverse:
                text.append(query[4])
            else:
                text.appendleft(query[4])
        else:
            if is_reverse:
                text.appendleft(query[4])
            else:
                text.append(query[4])

if is_reverse:
    print(''.join(text)[::-1])
else:
    print(''.join(text))
### BUGGY CODE ###

from heapq import heappush, heappop, heapify

def main():
    n, m = map(int, input().split())
    edges = [[] for _ in range(n)]
    isRoot = [True] * n
    for _ in range(n - 1 + m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        edges[a].append(b)
        isRoot[b] = False

    for i in range(n):
        if isRoot[i]:
            root = i
            break
    INF = 10 ** 20
    stack = [(0, root, -1)]
    heapify(stack)
    height = [-INF] * n
    parent = [None] * n
    def search(stack):
        score, node, par = heappop(stack)
        if -score > height[node]:
            height[node] = -score
            parent[node] = par
            for to in edges[node]:
                heappush(stack,(score - 1, to, node))

    while stack:
        search(stack)

    for i in range(n):
        print(parent[i] + 1)

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
revEdges = [[] for _ in range(n)]
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    edges[a].append(b)
    revEdges[b].append(a)

visited = [False] * n
lst = []
def search(x):
    if not visited[x]:
        visited[x] = True
        for to in edges[x]:
            search(to)
        lst.append(x)

for i in range(n):
    search(i)
lst.reverse()
dic = {}
for i in range(n):
    dic[lst[i]] = i

parent = [-1] * n
for i in lst:
    if not revEdges[i]:
        continue
    maxScore = -1
    index = -1
    for fr in revEdges[i]:
        if maxScore <= dic[fr]:
            maxScore = dic[fr]
            index = fr
    parent[i] = index

for i in range(n):
    print(parent[i] + 1)
### BUGGY CODE ###

import sys
from fractions import Fraction
import math
import heapq
input = sys.stdin.readline

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

s = sum(a)

w = [(k * a[i]) // s for i in range(n)]
b = [Fraction((w[i] + 1), a[i]) for i in range(n)]

r = k - sum(w)

heapq.heapify(b)
#print(b)

for i in range(r):
    x = heapq.heappop(b)
    heapq.heappush(b, Fraction(x.numerator+1, x.denominator))

y = heapq.heappop(b)

print(math.ceil(Fraction(y.denominator, y.numerator)))

### FIXED CODE ###

import sys
from fractions import Fraction
import math
import heapq
input = sys.stdin.readline

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

s = sum(a)

w = [(k * a[i]) // s for i in range(n)]
b = [Fraction((w[i] + 1), a[i]) for i in range(n)]

r = k - sum(w)

heapq.heapify(b)
#print(b)

for i in range(r):
    x = heapq.heappop(b)
    heapq.heappush(b, Fraction(x.numerator+1, x.denominator))

y = heapq.heappop(b)

print(math.ceil(Fraction(y.denominator, y.numerator)))
### BUGGY CODE ###

# coding: utf-8
from collections import deque
n = int(input())
a = deque(list(map(int, input().split())))
for i in range(n):
    num = 0
    b = a.popleft()
    for j in range(n):
        c = a.count(j)
        num += int(c*(c-1)/2)
    print(num)
    a.append(b)

### FIXED CODE ###

# coding: utf-8
n = int(input())
A = list(map(int, input().split()))
X = [0]*(n+1)
for a in A:
    X[a] += 1
s = 0
for x in X:
    s += x*(x-1)//2
for a in A:
    print(s-X[a]+1)
### BUGGY CODE ###

N = int(input())
ans = sum([x for x in range(N)])
print(ans)

### FIXED CODE ###

N = int(input())
ans = N*(N-1)//2
print(ans)
### BUGGY CODE ###

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

xh.sort()

ends = []
start = 0
# loop = 0
for base in range(n):
    for start, (x, _) in enumerate(xh[start:], start):
        # loop += 1
        if x > xh[base][0] + 2 * d:
            # start -= 1 # in range
            break
    else:
        start = n
    ends.append(start)
#     print(start)
# print(ends)
# print(loop, "loop")

cnt = [0] * (n + 1)

hist = 0
ans = 0
for i, end in enumerate(ends):
    hist += cnt[i]
    atk = (max(0, xh[i][1] - hist * a) + a - 1) // a
    # print(atk, "atk", hist, end=" ")
    ans += atk
    hist += atk

    cnt[i] += atk
    cnt[end] -= atk
    # print(":", cnt)

print(ans)
# print(cnt)
#
# import functools
# import operator
# print(functools.reduce(operator.add, cnt[:-1]), ans)


### FIXED CODE ###

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

xh.sort()

ends = [None] * n
start = 0
# loop = 0
d2 = 2 * d
for base in range(n):
    while True:
        if start >= n:
            break

        x = xh[start][0]
        # loop += 1
        if x > xh[base][0] + d2:
            # start -= 1 # in range
            break
        start += 1
    # for start, (x, _) in enumerate(xh[start:], start):
    #     loop += 1
    #     if x > xh[base][0] + 2 * d:
    #         # start -= 1 # in range
    #         break
    # else:
    #     start = n
    ends[base] = start
#     print(start)
# print(ends)
# print(loop, "loop")

cnt = [0] * (n + 1)

hist = 0
ans = 0
for i, end in enumerate(ends):
    hist += cnt[i]
    atk = (max(0, xh[i][1] - hist * a) + a - 1) // a
    # print(atk, "atk", hist, end=" ")
    ans += atk
    hist += atk

    cnt[i] += atk
    cnt[end] -= atk
    # print(":", cnt)

print(ans)
# print(cnt)
#
# import functools
# import operator
# print(functools.reduce(operator.add, cnt[:-1]), ans)
### BUGGY CODE ###

n, m = map(int, input().split())
arr = []
for _ in range(n):
    a, b = map(int, input().split())
    arr.append((a, b, 0))


arr.sort(key=lambda x: x[0])
arr.sort(key=lambda x: x[1], reverse=True)

res = 0
for m_i in range(1, m + 1):
    for x in range(len(arr)):
        a, b, deleted = arr[x]
        if deleted:
            continue
        if a <= m_i:
            res += b
            arr[x] = a, b, 1
            break
print(res)


### FIXED CODE ###

from heapq import heappush, heappop
n, m = map(int, input().split())

in_dict = {}
for _ in range(n):
    a, b = map(int, input().split())
    in_dict[a] = in_dict.get(a, [])
    in_dict[a].append(b)

heap = []
res = 0
for m_i in range(1, m + 1):
    for i in in_dict.get(m_i, []):
        heappush(heap, -i)
    if heap:
        res += -heappop(heap)

print(res)