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

import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
heapq.heapify(a)
for i in range(m):
    b,c=map(int,input().split())
    for j in range(b):
        if a[0]<c:
            heapq.heappop(a)
            heapq.heappush(a,c)
        else:
            break
print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1],reverse=True)
for b,c in bc:
    a.extend([c]*b)
    if len(a)>2*n:
        break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    for k in range(j + 1, n):
      if l[k] >= l[i] + l[j]:
        break
      ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
l_list = list(map(int, input().split()))
l_list.sort()
count = [0 for i in range(2000)]
cum = [0 for i in range(2000)]
for l in l_list:
  count[l] += 1
for i in range(1, 2000):
  cum[i] = cum[i - 1] + count[i]

ans = 0
cnt = 0
for i in range(n - 2):
  for j in range(i + 1, n - 1):
    ans += cum[l_list[i] + l_list[j] - 1] - j - 1
print(ans)
### BUGGY CODE ###

N,W = map(int, input().split())
v_max = (10**3)*(N+1)
inf = float('inf')
dp = [inf for _ in range(v_max+1)]
dp[0] = 0
for _ in range(N):
	w,v = map(int, input().split())
	for j in range(v_max,-1,-1):
		if j==0:
			dp[j] = 0
		else:
			a = dp[j]
			b = w + dp[j-v]		
			if v>j:
				dp[j] = a
			else:
				dp[j] = min(a,b)
ans = None
for i in range(v_max,-1,-1):
	z = dp[i]
	if z<=W and z!=inf:
		ans = i
		break
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
N,W = map(int, input().split())
v_max = (10**3)*N
inf = float('inf')
dp = [inf for _ in range(v_max+1)]
dp[0] = 0
for _ in range(N):
	w,v = map(int, input().split())
	for j in range(v_max,v-1,-1):
		b = w + dp[j-v]		
		if b<dp[j]:
			dp[j] = b

ans = None
for i in range(v_max+1):
	z = dp[i]
	if z<=W:
		ans = i

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

x=input().split()
h=int(x[0])
w=int(x[1])
d=int(x[2])
grid=[[]*w for i in range(h)]
for i in range(h):
    y=input().split()
    x=0
    while x<w:
        y[x]=int(y[x])
        x=x+1
    grid[i].extend(y)
coor=[[]*2 for i in range(h*w)]
for i in range(h):
    for j in range(w):
        coor[grid[i][j]-1].append(i)
        coor[grid[i][j]-1].append(j)
q=int(input())
for ii in range(q):
    x=input().split()
    l=int(x[0])
    r=int(x[1])
    cost=0
    while l!=r:
        cost+=abs(coor[l+d-1][0]-coor[l-1][0])+abs(coor[l+d-1][1]-coor[l-1][1])
        l+=d
    print(cost)

### FIXED CODE ###

x=input().split()
h=int(x[0])
w=int(x[1])
d=int(x[2])
grid=[[]*w for i in range(h)]
for i in range(h):
    y=input().split()
    x=0
    while x<w:
        y[x]=int(y[x])
        x=x+1
    grid[i]=y
coor=[[]*2 for i in range(h*w)]
for i in range(h):
    for j in range(w):
        coor[grid[i][j]-1]=[i,j]
cost=[0*i for i in range(h*w-d)]
for i in range(h*w-d):
    cost[i]=abs(coor[i+d][0]-coor[i][0])+abs(coor[i+d][1]-coor[i][1])
ans=[0*i for i in range(h*w)]
for i in range(d,h*w):
    ans[i]=ans[i-d]+cost[i-d]
q=int(input())
for ii in range(q):
    x=input().split()
    l=int(x[0])
    r=int(x[1])
    print(ans[r-1]-ans[l-1])
### BUGGY CODE ###

import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
p = list(map(float, input().split()))

#dp[i][j]は最初のi枚まで投げてj枚表になる確率
#初期化
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
#初期条件 0枚投げたとき0枚表→1
dp[0][0] = 1

for i in range(N):
    for j in range(N):
        dp[i+1][j] += dp[i][j] * (1 - p[i])
        dp[i+1][j+1] += dp[i][j] * p[i]

#i == N で j >= (N+1)/2 のものを足し合わせる
ans = 0
for j in range((N+1)//2, N+1):
    ans += dp[N][j]
print(ans)

### FIXED CODE ###

import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

N = int(input())
p = list(map(float, input().split()))

#dp[i][j]は最初のi枚まで投げてj枚表になる確率
#初期化
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
#初期条件 0枚投げたとき0枚表→1
dp[0][0] = 1

for i in range(N):
    for j in range(N):
        dp[i+1][j] += dp[i][j] * (1 - p[i])
        dp[i+1][j+1] += dp[i][j] * p[i]

#i == N で j >= (N+1)/2 のものを足し合わせる
ans = 0
for j in range((N+1)//2, N+1):
    ans += dp[N][j]
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A = [i-1 for i in A]

doubling = [[0] * N for _ in range(61)]
for i in range(N):
  doubling[0][i] = A[i]
  
for i in range(1,61):
  for j in range(N):
    doubling[i][j] = doubling[i-1][doubling[i-1][j]]
    
now = 0
i = 0
while K!=0:
  if K&1==1:
    now = doubling[i][now]
    K = K>>1
    i += 1
    
  else:
    K = K>>1
    i += 1
    
print(now+1)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A = [i-1 for i in A]

flag = [False]*N
from collections import deque

q = deque([])
q.append(0)
flag[0] = True
now = 0
while True:
  now = A[now]
  if flag[now]:
    break
  else:
    flag[now] = True
    q.append(now)
    
l = list(q)
if K<len(l):
  print(l[K]+1)

else:
  for i,x in enumerate(l):
    if x==now:
      l = l[i:]
      K -= i
      break
  
  print(l[K%len(l)]+1)
### BUGGY CODE ###

import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
AB = [lr() for _ in range(N)]
#Bが報酬
AB = [(a, b) for a, b in AB if a<=M]
AB.sort(reverse=True, key=lambda x: x[1])
AB = deque(AB)
answer = 0
used = set()
out = set()
while AB:
    x, y = AB.popleft()
    if x > M or x in out:
        continue
    else:
        z = x
        while z in used:
            z += 1
        if z > M:
            out.add(x)
            continue
        used.add(z)
        answer += y

print(answer)
        

### FIXED CODE ###

import heapq

n,m=map(int,input().split())
jobs=[[] for _ in range(m)]
for i in range(n):
    d,r=map(int,input().split())
    if d-1<m:
        jobs[d-1].append(-r)
rewards=0
heap=[]
for i in range(m):
    for reward in jobs[i]:
        heapq.heappush(heap,reward)
    if len(heap)>0:
        rewards+=-heapq.heappop(heap)

print(rewards)
### BUGGY CODE ###

#! /usr/bin/env python3
def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    G = []
    for i in range(H):
        G += [[[0,1][x=='#']for x in input()]]

    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]


    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    s = set()
    
    while f:
        f = False
        while q:
            t = []
            for y, x in q:
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        
        for y, x in a:
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and (py,px) not in s:
                    s.add((py,px))
                    b += [(py, px)]
                    q += [(py, px)]
        # for i in G:
        #     print(i)
        # print()
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

main()



### FIXED CODE ###

#! /usr/bin/env python3
def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    G = []
    for i in range(H):
        G += [[[0,1][x=='#']for x in input()]]

    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]


    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    while f:
        f = False
        while q:
            t = []
            for y, x in q:
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        s = set()
        for y, x in a:
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and (py,px) not in s:
                    s.add((py,px))
                    b += [(py, px)]
                    q += [(py, px)]
        # for i in G:
        #     print(i)
        # print()
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
 
b=list(set(a))
c=0
for i in range(len(b)):
    er = a.count( b[i] ) - b[i]
    if er<0:
        c+= er + b[i]
    else:
        c+=er
print(c)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
counter=Counter(a)
b=list(set(a))
c=0
for i in b:
    k =  counter[i]
    c+= k-i if k-i>=0 else k
print(c)
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
q = int(input())
li = ["", s]
cur = 1
for _ in range(q):
    query = input().split()
    if query[0] == "1":
        cur ^= 1
    else:
        f, c = query[1:]
        if f == "1":
            li[cur ^ 1] += c
        else:
            li[cur] += c
ans = li[0][::-1] + li[1]
if cur == 0:
    ans = ans[::-1]
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque

s = input()
q = int(input())
deq = deque(s)
cur = 1
for _ in range(q):
    query = input().split()
    if query[0] == "1":
        cur ^= 1
    else:
        f, c = query[1:]
        f = int(f) - 1
        if cur ^ f:
            deq.appendleft(c)
        else:
            deq.append(c)
ans = ""
while len(deq) > 0:
    ans += deq.popleft() if cur else deq.pop()
print(ans)
### BUGGY CODE ###

def main():
    number = int(input())
    num_list = list(map(int, input().split()))
    total = sum([num_list[i]*num_list [j]for i in range(number) for j in range(i+1, number)])
    div = total // (10**9 + 7)
    print(total - div * (10**9 + 7))
if __name__ == '__main__':
    main()

### FIXED CODE ###

from sys import stdin
import itertools
def main():
    number = int(input())
    num_list = list(map(int, stdin.readline().split()))
    num_list_sum = sum(num_list)
    total = 0
    for i in range(number):
        num_list_sum -= num_list[i]
        total += num_list[i] * num_list_sum
    print(total % (10**9+7))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

def main():
  s=input()
  q=int(input())
  count=0
  for _ in [0]*q:
    a=list(input().split())
    if len(a)==1:
      count+=1
    else:
      if count%2==0:
        if a[1]=='1':
          l=(a[2],s)
          s=''.join(l)
        else:
          l=(s,a[2])
          s=''.join(l)
      else:
        if a[1]=='1':
          l=(s,a[2])
          s=''.join(l)
        else:
          l=(a[2],s)
          s=''.join(l)
  if count%2==1:
    s=s[::-1]
  print(s)
if __name__=='__main__':
  main()


### FIXED CODE ###

def main():
  from collections import deque
  s=deque(input())
  q=int(input())
  count=0
  for _ in [0]*q:
    a=list(input().split())
    if len(a)==1:
      count+=1
    else:
      if count%2==0:
        if a[1]=='1':
           s.appendleft(a[2])
        else:
          s.append(a[2])
      else:
        if a[1]=='1':
          s.append(a[2])
        else:
          l=(a[2],s)
          s.appendleft(a[2])
  if count%2==1:
    s=list(s)[::-1]
  print(''.join(s))
if __name__=='__main__':
  main()
### BUGGY CODE ###

in_li = list(map(int,input().split()))
A = in_li[0]
B = in_li[1]
K = in_li[2]
if A + B == K :
    print("0 0")
elif A > K :
    print(A-K,"",B)
else :
    for i in range(K) :
        if A != 0 :
            A -= 1
        elif B != 0 :
            B -= 1
        else :
            pass
    print(A,"",B)


### FIXED CODE ###

in_li = list(map(int,input().split()))
A = in_li[0]
B = in_li[1]
K = in_li[2]
if A + B <= K :
    print("0 0")
else :
    if A > K :
        print(A-K,"",B)
    elif B > K - A :
        print("0",B-(K-A))
### BUGGY CODE ###

def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def main():
    n,k = readInts()
    A = readInts()

    setA = list(set(A))
    if len(setA) <= k:
        print(0)
        exit()

    sLen = len(setA)
    # ここを何とかしよう
    kosu = [0] * sLen
    i = 0
    while i < sLen:
        kosu[i] = A.count(setA[i])
        i += 1
    #print(*kosu)
    # -----------------
    kosu = sorted(kosu)
    ans = 0
    #print(*ALL)
    for i in range(sLen-k):
        ans += kosu[i]
    print(ans)
if __name__ == '__main__':
  main()


### FIXED CODE ###

import collections
#aa = collections.Counter(a) # list to list

def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def main():
    n,k = readInts()
    A = readInts()
    A_qu = collections.Counter(A)
    ALL = []
    for i in A_qu:
        ALL.append(A_qu[i])
    ALL = sorted(ALL)
    ans = 0
    for i in range(len(ALL) - k):
        ans += ALL[i]
    print(ans)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))

s = []
for i in range(1,N+1):
  s.append(A.index(i)+1)
  
[print(x, end=' ') for x in s]

### FIXED CODE ###

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

l = [0]*N
for i,a in enumerate(A):
  l[a-1]=i+1
  
for x in l:
  print(x, end=' ')
### BUGGY CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    import numpy as np
    N = int(input())
    A = np.array(list(map(int, input().split())))

    #output
    answer = 0
    for i in range(N):
        if N - np.count_nonzero(A[i] % A) > 1:
            answer += 1
    answer = N - answer
    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()


### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))

    #output
    from collections import Counter
    M = max(A) + 1
    B = [True] * (M+1)
    A = sorted(A)
    C = Counter(A)

    answer = 0
    for a in A:
        if B[a]:
            for j in range(a, M, a):
                B[j] = False
            if C[a] > 1:
                continue
            else:
                answer += 1

    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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


l=[]
for i in range(n):
  l.append(sum(p[i:i+k]))

ans=0.0
max=l.index(max(l))
for i in range(k):
  ans+=sum(list(range(1,p[max+i]+1)))/p[max+i]
  
print(ans)


### FIXED CODE ###

import numpy as np
n,k=map(int, input().split())
p=list(map(int,input().split()))


s=[]
p=np.array(p)
sum=0
for i in range(n):
  sum+=(1+p[i])/2
  s.append(sum)
#print(s)
if k==n:
  print(s[-1])
  exit()
max=s[k-1]-s[0]
for j in range(1,n-k):
  #print(j)
  if max<= s[j+k]-s[j]:
    max=s[j+k]-s[j]
  
print(max)
### BUGGY CODE ###


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

RD = []
end = [False] * N

for i in range(N):

    RD.append([])

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q = [endp] 
    else:
        continue

    while len(Q) > 0:

        q = Q.pop(0)
        end[q] = False

        if cor[q] == "x":
            cor[q] = 0

        for r,d in RD[q]:

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        if ans == "No":
            break

    if ans == "No":
        break

print (ans)


### FIXED CODE ###

from collections import deque

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

RD = [deque() for i in range(N)]
end = [False] * N

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = deque()

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q.append(endp)


        while len(Q) > 0:

            q = Q.pop()
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    print ("No")
                    exit()


print ("Yes")
### BUGGY CODE ###

R, C, K = map(int, input().split())
a = [[0]*C for _ in range(R)]
dp = [[[0]*4 for _ in range(C+5)] for _ in range(R+5)]
for i in range(K):
    r, c, v = map(int, input().split())
    a[r-1][c-1] = v

for i in range(R):
    for j in range(C):
        for k in range(2, -1, -1):
            dp[i][j][k+1] = max(dp[i][j][k+1], dp[i][j][k]+a[i][j])
        for k in range(4):
            dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k])
            dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])

ans = 0
for i in range(4):
    ans = max(ans, dp[R-1][C-1][i])

print(ans)



### FIXED CODE ###

r,c,k = list(map(int, input().split()))
import copy
dp=[[[0]*4 for _ in range(c)] for _ in range(2)]


F = [[0]*c for _ in range(r)]

for _ in range(k):
  x,y,v = list(map(int, input().split()))
  x-=1
  y-=1
  F[x][y] = v
  
for nn in range(r):
  for j in range(c):
    i = 1
    val = F[nn][j]
  
      
    mxv = max(dp[i-1][j][0], dp[i-1][j][1], dp[i-1][j][2], dp[i-1][j][3])

    dp[i][j][3] = max(dp[i][j-1][3], dp[i][j-1][2] + val)
    dp[i][j][2] = max(dp[i][j-1][2], dp[i][j-1][1] + val)
    dp[i][j][1] = max(dp[i][j-1][1], dp[i][j-1][0] + val, mxv + val)
    dp[i][j][0] = mxv

  dp[0] = dp[1] 
  dp[1] = [[0]*4 for _ in range(c)]

best = 0


for k in range(4):
  best = max(best, dp[0][c-1][k])
    
print(best)
### BUGGY CODE ###

n = int(input())

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

x = ab[0][0]
y = ab[0][1]
j = 1
flg = True
for i in range(1,n):
    xx = ab[i][0]
    yy = ab[i][1]
    while flg:
        if x> j*xx or y > j*yy:
            j +=1
        else:
            x = xx *j
            y = yy *j
            break
    j = 1

print(x+y)

### FIXED CODE ###

n = int(input())

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

x = ab[0][0]
y = ab[0][1]
j = 1
flg = True
for i in range(1,n):
    xx = ab[i][0]
    yy = ab[i][1]
    j = max(x//xx,y//yy)
    while flg:
        if x> j*xx or y > j*yy:
            j +=1
        else:
            x = xx *j
            y = yy *j
            break

print(x+y)
### BUGGY CODE ###

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

array = []
for i in range(N):
    n = i+1
    nankai = 0
    while n < K:
        n*2
        nankai += 1
    array.append(nankai)

kakus = 0
for k in array:
    kaku = (1/N)
    for q in range(k):
        kaku * (1/2)
    kakus += kaku

print(kakus)

### FIXED CODE ###

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

array = []
for i in range(N):
    n = i+1
    nankai = 0
    while n < K:
        n = n * 2
        nankai += 1
    array.append(nankai)

kakus = 0
for k in array:
    kaku = 1 / N
    for q in range(k):
        kaku = kaku / 2
    kakus += kaku

print(kakus)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

S.sort()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    if S[i][1] % A == 0:
        dmg = S[i][1]
        cnt += S[i][1] // A
    else:
        dmg = A * (S[i][1]//A + 1)
        cnt += S[i][1]//A + 1
    max_X = S[i][0] + D*2
    j = i + 1
    while j < N:
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg
        j += 1

print(cnt)


### FIXED CODE ###

from collections import deque
import math

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
S = [0]*N
atack = deque()
for i in range(N):
    x, h = map(int, input().split())
    S[i] = [x, h]

S.sort()
cnt = 0
dmg = 0
for i in range(N):
    while atack:
        if atack[0][0] < S[i][0]:
            x, d = atack.popleft()
            dmg -= d
        else:
            break

    if S[i][1] <= dmg:
        continue
    bomb = math.ceil((S[i][1]-dmg)/A)
    atack.append([S[i][0]+2*D, A*bomb])
    cnt += bomb
    dmg += A*bomb

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

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

MOD = 10 ** 9 + 7

ans = 0
d = 1
for _ in range(60):
    x = 0
    for i in range(n):
        x += a[i] % 2
        a[i] >>= 1
    ans = (((x * (n-x)) % MOD) * d % MOD + ans) % MOD
    d = d * 2 % MOD

print(ans)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7

ans = 0
d = 1
for _ in range(60):
    x = 0
    for i in range(n):
        x += a[i] % 2
        a[i] //= 2
    ans = (((x * (n-x)) % MOD) * d % MOD + ans) % MOD
    d = d * 2 % MOD

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

N,M = map(int,input().split())
path = [[] for _ in range(N*3+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v+N)
    path[u+N].append(v+N+N)
    path[u+N+N].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [-1 for _ in range(N*3+3)]
def bfs():
    while len(q) > 0:
        now,cnt = q.popleft()
        #print(now,T,cnt,path[now],q)
        vis[now] = cnt
        if now == T: 
            return cnt
        [q.append((x,cnt+1)) for x in path[now] if vis[x] == -1]
        #for x in path[now]:
         #   if vis[x] == -1:
          #      q.append((x,cnt+1))
    return -3
vis[S] = 1
q.append([S,0])
print(bfs()//3)




### FIXED CODE ###

N,M = map(int,input().split())
import time
start_t = time.time()
path = [[] for _ in range(N+3)]
for _ in range(M):
    u,v = map(int,input().split())
    path[u].append(v)

S,T = map(int,input().split())
import collections

q = collections.deque()
vis = [[-1 for _ in range(3)] for _ in range(N+3)]
vis[S][0] = 1
q.append([S,0])
while len(q):
    now,cnt = q.popleft()
    step = cnt % 3
    for x in path[now]:
        if vis[x][(step+1)%3] < 0:
            vis[x][(step+1)%3] = cnt
            q.append((x,cnt+1))

if vis[T][0] == -1:
    print(-1)
else:
    print(vis[T][0]//3+1)
### BUGGY CODE ###

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

r=s.count("R")
g=s.count("G")
b=s.count("B")

ans=r*g*b
for i in range(1,n):
    for j in range(n):
        if(j+i*2>=n):continue
        d1,d2,d3=s[j],s[j+i],s[j+i*2]
        if(not(d1==d2 or d2==d3 or d1==d3)):ans-=1
print(ans)

### FIXED CODE ###

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

r=s.count("R")
g=s.count("G")
b=n-r-g

ans=r*g*b
for i in range(1,n):
    for j in range(n):
        if(j+i*2>=n):break
        d1,d2,d3=s[j],s[j+i],s[j+i*2]
        if(not(d1==d2 or d2==d3 or d1==d3)):ans-=1
print(ans)