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

N = int(input())
S = str(input())

num = [[0]*N for i in range(3)]
if S[N-1] == 'R':
    num[0][N-1] += 1
elif S[N-1] == 'G':
    num[1][N-1] += 1
else:
    num[2][N-1] += 1
    
for i in range(2,N+1):
    num[0][-i] = num[0][-i+1]
    num[1][-i] = num[1][-i+1]
    num[2][-i] = num[2][-i+1]
    if S[-i] == 'R':
        num[0][-i] += 1
    elif S[-i] == 'G':
        num[1][-i] += 1
    else:
        num[2][-i] += 1

ans = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        if S[i] != S[j]:
            if S[i] != 'R' and S[j] != 'R':
                ans += num[0][j+1]
                if 2*j - i < N:
                    if S[2*j - i] == 'R':
                        ans -= 1
                        
            elif S[i] != 'G' and S[j] != 'G':
                ans += num[1][j+1]
                if 2*j - i < N:
                    if S[2*j - i] == 'G':
                        ans -= 1
                        
            elif S[i] != 'B' and S[j] != 'B':
                ans += num[2][j+1]
                if 2*j - i < N:
                    if S[2*j - i] == 'B':
                        ans -= 1
                    
print(int(ans))

### FIXED CODE ###

N = int(input())
S = str(input())
R,G,B = 0,0,0
for i in range(N):
    if S[i] == 'R':
        R += 1
    elif S[i] == 'B':
        B += 1
    else:
        G += 1

exc = 0
for j in range(1,N-1):
    num = 1
    while 0 <= j-num and j+num < N:
        if S[j-num] != S[j+num] and  S[j-num] != S[j] and  S[j] != S[j+num]:
            exc += 1
        num += 1

print(int(R*B*G - exc))
### BUGGY CODE ###

n = int(input())
li = list(map(int, input().split()))
res = ''
for i in range(1,n+1):
    res += str(li.count(i))+'\n'
print(res)

### FIXED CODE ###

import collections
n = int(input())
li = list(map(int, input().split()))
cnt = dict(collections.Counter(li))
for i in range(1,n+1):
    print(cnt.get(i, 0))
### BUGGY CODE ###

import sys
import collections
sys.setrecursionlimit(10**7)

def cur(x):
    for i in dd[x]:
        if dd[x][i]==-1: continue
        dd[i][x]=-1
        ans[i]+=ans[x]
        cur(i)

n,q=map(int,input().split())
dd=collections.defaultdict(dict)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    dd[a][b]=1
    dd[b][a]=1

for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

cur(1)
print(*ans[1:])

### FIXED CODE ###

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

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


for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

visit=[True]*(n+1)
tmp=[1]
for x in tmp:
    visit[x]=False
    for y in neighbor[x]:
        if visit[y]:
            tmp.append(y)
            ans[y]+=ans[x]

print(*ans[1:])
### BUGGY CODE ###

mod=1000000007
n,m=map(int,input().split())
a=[]
af=0
for i in range(m):
    a.append(int(input()))
if len(a)>0:
    a.sort()
    af=1
f=0
for i in range(len(a)):
    if a[i]+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if af==1 and len(a)>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
  

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)


f=0
for i in range(al-1):
    if a[i+1]==a[i]+1:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
### BUGGY CODE ###

X = int(input())

x = [0]
y = [0]
t = X
ans = 1
while True:
    ans += 1
    x.append(t)
    y.append(t)
    if (180-t)%360 in x:
        if t == (180-t)%360 and x.count(t) == 1:
            t += X
            t %= 360
            continue
        x.remove((180-t)%360)
        x.remove(t)
    elif (180+t) in x:
        if t == (180+t)%360 and x.count(t) == 1:
            t += X
            t %= 360
            continue
        x.remove((180-t)%360)
        x.remove(t)
    if (-t)%360 in y:
        if t == (-t)%360 and y.count(t) == 1:
            t += X
            t %= 360
            continue
        y.remove((-t)%360)
        y.remove(t)
    elif (180+t) in y:
        if t == (180-t)%360 and y.count(t) == 1:
            t += X
            t %= 360
            continue
        y.remove((180-t)%360)
        y.remove(t)
    if len(x) == 0 and len(y) == 0:
        break
    t += X
    t %= 360
print(ans//2)

### FIXED CODE ###

X = int(input())

ans = 360
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

ans = 360 // gcd(X, 360)
print(ans)
### BUGGY CODE ###

K, S = [int(n) for n in input().split()]
print(sum([1 for X in range(K+1) for Y in range(K+1) for Z in range(K+1) if X+Y+Z==S]))

### FIXED CODE ###

K, S = [int(n) for n in input().split()]
print(sum([1 for X in range(K+1) for Y in range(K+1) if 0<=S-X-Y<=K]))
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.sort(list(map(int,input().split())))[::-1]
ans = 0
i = 0
while i < N-2:
    j = i+1
    while j < N-1:
        a = A[i]
        b = A[j]
        C = A[j+1:]
        J = (C>a-b)
        if (np.any(J)):
            ans += np.size(C[J])
        j += 1
    i += 1

print(ans)

### FIXED CODE ###

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

#N=len(sticks)
sticks = sorted(sticks1, reverse=True)
#sticks.sort(reverse = True)
count = 0
jmax = N-2
kmax = N-1
i=0
while i<N-2:
    j= i+1
    while j<jmax+1:
        k=kmax
        while j<k:
            #sticks[i]>sticks[j]>sticks[k]
            if sticks[i]<sticks[j]+sticks[k]:
                count += k-j
                kmax = k
                break
            else:
                k -= 1
                continue
        jmax = kmax-1
        j += 1
    kmax = N-1
    jmax = N-2
    i += 1
      
print(count)
### BUGGY CODE ###

import bisect

N=int(input().strip())
L=list(map(int,input().strip().split()))
L.sort()

MAX=L[-1]
count=0
for i in range(N-2):
    for  j in range(i+1,N-1):
        # print(i,j)
        # print(L[i+1:-1])
        minInd=j+1
        # print(minInd)
        
        # if L[minInd]> L[i]+L[j]:
        #     continue
        # if MAX<L[i]+L[j]:
        #     count+=N-1-minInd+1
        # else:
        #     ind = bisect.bisect_left(L[minInd:], L[i]+L[j]) # number of < a+b
        #     count+=ind
        
        ind = bisect.bisect_left(L[minInd:], L[i]+L[j]) # number of < a+b
        count+=ind
print(count)

### FIXED CODE ###

import bisect
 
N = int(input())
L = list(map(int, input().split()))
L.sort()
 
c = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    c += bisect.bisect_right(L, L[i]+L[j]-1) - j - 1
 
 
print(c)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

div = 1000000007

n, m, *a = map(int, read().split())

f = [0] * (n + 1)
f[0] = 1

if 1 not in a:
    f[1] = 1
 
for i in range(2, n + 1):
    if i in a:
        continue
    f[i] = (f[i - 1] + f[i - 2]) % div
 
print(f[-1])


### FIXED CODE ###

def main():
    N, M, *a = map(int, open(0).read().split())
    div = 1000000007
    broken = set(a)
 
    comb_list = [0] * (N + 1)
    comb_list[0] = 1
    if 1 not in broken:
        comb_list[1] = 1
 
    for i in range(2, N + 1):
        if i in broken:
            continue
        comb_list[i] = (comb_list[i - 1] + comb_list[i - 2]) % div
 
    print(comb_list[-1])
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###


MOD = 1000000007

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return a*b//gcd(a,b)

def main():
    n = int(input())
    a = list(map(int,input().split()))
    all_lcm = a[0]
    for i in range(n):
        all_lcm = lcm(all_lcm, a[i])
    ans = 0
    for i in range(n):
        ans += all_lcm//a[i]
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###


MOD = 1000000007

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return a//gcd(a,b)*b

n = int(input())
a = list(map(int,input().split()))
all_lcm = 1
for i in range(n):
    all_lcm = lcm(all_lcm, a[i])
ans = 0
for i in range(n):
    ans += all_lcm//a[i]
print(ans%MOD)
### BUGGY CODE ###

a, b, c, d = map(int, input().split())
mod = 998244353

dp = [[0 for _ in range(c - a + 1)] for _ in range(d - b + 1)]
dp[0][0] = 1
for j in range(c - a + 1):
    for i in range(d - b + 1):
        if i == j == 0:
            dp[i][j] = 1
        elif i == 0:
            dp[i][j] = dp[i][j - 1] * b % mod
        elif j == 0:
            dp[i][j] = dp[i - 1][j] * a % mod
        else:
            dp[i][j] = ((j + a - 1) * dp[i - 1][j] + (i + b - 1) * dp[i][j - 1] - dp[i - 1][j - 1] * (i + b - 1) * (j + a - 1) + dp[i - 1][j] + dp[i][j - 1]) % mod
print(dp[-1][-1])

### FIXED CODE ###

a, b, c, d = map(int, input().split())
mod = 998244353

dp = [[0 for _ in range(c - a + 1)] for _ in range(d - b + 1)]
dp[0][0] = 1
for j in range(c - a + 1):
    for i in range(d - b + 1):
        if i == j == 0:
            dp[i][j] = 1
        elif i == 0:
            dp[i][j] = dp[i][j - 1] * b % mod
        elif j == 0:
            dp[i][j] = dp[i - 1][j] * a % mod
        else:
            tmp1 = (j + a - 1) * dp[i - 1][j] % mod
            tmp2 = (i + b - 1) * dp[i][j - 1] % mod
            tmp3 = -dp[i - 1][j - 1] * (i + b - 1) * (j + a - 1) % mod
            tmp4 = (dp[i - 1][j] + dp[i][j - 1]) % mod
            dp[i][j] = (tmp1 + tmp2 + tmp3 + tmp4) % mod
print(dp[-1][-1])
### BUGGY CODE ###

A,B,M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
m=[]
for i in range(M):
    array = list(map(int, input().strip().split()))
    m.append(array)

def hitachi02(a,b,m):
    results=[]
    for i in range(len(a)):
        for j in range(len(b)):
            for k in range(len(m)):
                if i+1 == m[k][0] and j+1 == m[k][1]:
                    cal = a[i]+b[j]-m[k][2]
                else:
                    cal = a[i]+b[j]
                results.append(cal)
    result=min(results)
    return result

result=hitachi02(a,b,m)
print(result)

### FIXED CODE ###

A,B,M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
m=[]
for i in range(M):
    array = list(map(int, input().strip().split()))
    m.append(array)

def hitachi02(a,b,m):
    results=[]
    cal01=min(a)+min(b)
    for k in range(len(m)):
        results.append(a[m[k][0]-1]+b[m[k][1]-1]-m[k][2])
    cal02=min(results)
    if cal01>=cal02:
        return cal02
    else:
        return cal01

result=hitachi02(a,b,m)
print(result)
### BUGGY CODE ###

#!/usr/bin/python3

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7

#N = int(input())
#A = [int(x) for x in input().split()]
#V = [[0] * 100 for _ in range(100)]
def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x


def divisor_list(n):
    # ret = set()
    ret = dict()
    ret[1] = 1
    i=2
    while n!=1:
        while n % i == 0:
            ret[i] = ret.get(i,0) + 1
            n /= i
        i+=1
    return ret

A,B = [int(x) for x in input().split()]
dA = divisor_list(A)
dB = divisor_list(B)

cm = set(dA.keys()).intersection(set(dB.keys()))

print(len(cm))

### FIXED CODE ###

#!/usr/bin/python3

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7

#N = int(input())
#A = [int(x) for x in input().split()]
#V = [[0] * 100 for _ in range(100)]

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

A,B = [int(x) for x in input().split()]
dA = set(prime_decomposition(A))
dB = set(prime_decomposition(B))

cm = dA.intersection(dB)
cm.add(1)

print(len(cm))
### BUGGY CODE ###

n, m = map(int, input().split())
num = [list(map(int, input().split())) for _ in range(m)]
count = 0

for i in range(1, n+1):
  ans = 0
  for j in range(m):
    if i >= num[j][0] and i <= num[j][1]:
      ans += 1
    else:
      break
  if ans == m:
    count += 1

print(count)

### FIXED CODE ###

n, m = map(int, input().split())
num = [list(map(int, input().split())) for _ in range(m)]
num1 = 1
num2 = n

for j in range(m):
  num1 = max(num[j][0], num1)
  num2 = min(num[j][1], num2)

ans = num2 - num1 + 1

if ans > 0:
  print(ans)
else:
  print(0)
### BUGGY CODE ###

import sys
N,M = list(map(int,sys.stdin.readline().split()))
S = list(map(int,sys.stdin.readline().split()))
S = [0] + S
T = list(map(int,sys.stdin.readline().split()))
T = [0] + T
DP = [[0] * (N+1)  for _ in range(M+1)]
for n in range(N+1):
    DP[0][n] = 1
for m in range(M+1):
    DP[m][0] = 1
# s = 0
# for i in range(N+1):
#     for j in range(M+1):
#         if S[i] == T[j]:
#             for i2 in range(i):
#                 for j2 in range(j):
#                     dp[i][j] += dp[i2][j2]
#             s += dp[i][j]
# print(s)
mod = 10**9 + 7
for n in range(1,N+1):
    for m in range(1,M+1):
        num = DP[m-1][n-1] if S[n] == T[m] else 0
        DP[m][n] = (DP[m-1][n] + DP[m][n-1] + num - DP[m-1][n-1]) % mod
print(DP[M][N])

### FIXED CODE ###

N,M = list(map(int,input().split()))
S = list(map(int,input().split()))
S = [0] + S
T = list(map(int,input().split()))
T = [0] + T
dp = [[0] * (N+1)  for _ in range(M+1)]
DP = [[0] * (N+1)  for _ in range(M+1)]
dp[0][0] = 1
for n in range(N+1):
    DP[0][n] = 1
for m in range(M+1):
    DP[m][0] = 1
# s = 0
# for i in range(N+1):
#     for j in range(M+1):
#         if S[i] == T[j]:
#             for i2 in range(i):
#                 for j2 in range(j):
#                     dp[i][j] += dp[i2][j2]
#             s += dp[i][j]
# print(s)
for n in range(1,N+1):
    for m in range(1,M+1):
        if S[n] == T[m]:
            dp[m][n] = DP[m-1][n-1]
        DP[m][n] = (DP[m-1][n] + DP[m][n-1] + dp[m][n] - DP[m-1][n-1]) % (10**9+7)
print(DP[M][N])
### BUGGY CODE ###

num=int(input())
mm=[int(s) for s in input().split()]
total=sum(mm)


count=0
for j,i in enumerate(mm):
  count+=i
  if count>=total//2:
    flag=j
    break
p=0
q=sum([mm[i+1] for i in range(flag,len(mm)-1)])
while True:
  if count>q:
    q+=1
    p+=1
  else:
    break


mm.reverse()

count=0
for j,i in enumerate(mm):
  count+=i
  if count>=total//2:
    flag=j
    break
p2=0
q=sum([mm[i+1] for i in range(flag,len(mm)-1)])
while True:
  if count>q:
    q+=1
    p2+=1
  else:
    break

if p>=p2:
  print(p2)
else:
  print(p)

### FIXED CODE ###

num=int(input())
mm=[int(s) for s in input().split()]
total=sum(mm)


count=0
for j,i in enumerate(mm):
  count+=i
  if count>=total//2:
    flag=j
    break

q=sum(mm[flag+1:])

p=count-q


mm.reverse()

count=0
for j,i in enumerate(mm):
  count+=i
  if count>=total//2:
    flag=j
    break

q=sum(mm[flag+1:])
p2=count-q

if p>=p2:
  print(p2)
else:
  print(p)
### BUGGY CODE ###

from collections import Counter
import math


m2 = math.factorial(2)

def nC2(n):
    return math.factorial(n) // (math.factorial(n - 2) * m2)


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

ac = dict(Counter(a))

ans = 0
for k, v in ac.items():
    if v < 2:
        ac[k] = (v, 0, 0)
    else:
        c = nC2(v)
        ans += c
        if v - 1 < 2:
            ac[k] = (v, c, 0)
        else:
            ac[k] = (v, c, nC2(v - 1))

for i in a:
    v = ac[i]
    if v[0] - 1 < 2:
        print(ans - v[1])
    else:
        print(ans - v[1] + v[2])

### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce


def nCr(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


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

ac = dict(Counter(a))

ans = 0
for k, v in ac.items():
    if v < 2:
        ac[k] = (v, 0, 0)
    else:
        c = nCr(v, 2)
        ans += c
        if v - 1 < 2:
            ac[k] = (v, c, 0)
        else:
            ac[k] = (v, c, nCr(v - 1, 2))

for i in a:
    v = ac[i]
    if v[0] - 1 < 2:
        print(ans - v[1])
    else:
        print(ans - v[1] + v[2])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from heapq import heappush, heappop
def min_cost_flow_dijkstra(E, s, t, f):
    INF = 1 << 100
    NN = 2 * N + 6
    LN = NN.bit_length()
    G = [[] for _ in range(NN)]
    for a, b, cap, c in E:
        G[a].append([b, cap, c, len(G[b])])
        G[b].append([a, 0, -c, len(G[a])-1])
    prevv = [-1] * NN
    preve = [-1] * NN
    res = 0
    h = [0] * NN
    while f > 0:
        dist = [INF] * NN
        dist[s] = 0
        Q = []
        heappush(Q, s)
        while len(Q):
            x = heappop(Q)
            d, v = -(x>>LN), x % (1<<LN)
            if dist[v] < d: continue
            for i, (w, _cap, c, r) in enumerate(G[v]):
                if _cap > 0 and dist[w] > dist[v] + c + h[v] - h[w]:
                    dist[w] = dist[v] + c + h[v] - h[w]
                    prevv[w] = v
                    preve[w] = i
                    heappush(Q, (-dist[w] << LN) + w)
        if dist[t] == INF:
            return -1
        for v in range(N):
            h[v] += dist[v]
        
        d = f
        v = t
        while v != s:
            d = min(d, G[prevv[v]][preve[v]][1])
            v = prevv[v]
        f -= d
        res += d * dist[t]
        v = t
        while v != s:
            G[prevv[v]][preve[v]][1] -= d
            G[v][G[prevv[v]][preve[v]][3]][1] += d
            v = prevv[v]
    return res

E = []
N = int(input())
su = 0
inf = 1 << 31
for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((2*N+4, i, cnt, 0))
    E.append((i, 2*N, cnt, x + y + inf))
    E.append((i, 2*N+1, cnt, x - y + inf))
    E.append((i, 2*N+2, cnt, - x + y + inf))
    E.append((i, 2*N+3, cnt, - x - y + inf))
    su += cnt

for i in range(N):
    x, y, cnt = map(int, input().split())
    E.append((i+N, 2*N+5, cnt, 0))
    E.append((2*N, i+N, cnt, - x - y + inf))
    E.append((2*N+1, i+N, cnt, - x + y + inf))
    E.append((2*N+2, i+N, cnt, x - y + inf))
    E.append((2*N+3, i+N, cnt, x + y + inf))

print(su * inf * 2 - min_cost_flow_dijkstra(E, 2*N+4, 2*N+5, su))

### FIXED CODE ###

from networkx import*
N = int(input())
G = MultiDiGraph()
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(i, demand = -c)
    G.add_weighted_edges_from([(i, -1, x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -2, x - y)], capacity = c)
    G.add_weighted_edges_from([(i, -3, -x + y)], capacity = c)
    G.add_weighted_edges_from([(i, -4, -x - y)], capacity = c)
for i in range(N):
    x, y, c = map(int, input().split())
    G.add_node(N + i, demand = c)
    G.add_weighted_edges_from([(-1, N + i, -x - y)], capacity = c)
    G.add_weighted_edges_from([(-2, N + i, -x + y)], capacity = c)
    G.add_weighted_edges_from([(-3, N + i, x - y)], capacity = c)
    G.add_weighted_edges_from([(-4, N + i, x + y)], capacity = c)

print(-min_cost_flow_cost(G))
### BUGGY CODE ###

n,d,a=map(int,input().split())
x=[]
h=[]
xh=[]
for _ in range(n):
    i,j = map(int,input().split())
    xh.append((i,j))
xh = sorted(xh, key=lambda x: x[0])
c=[]
ans=0
max_=[]
for i in range(n):
    value = xh[i][1]
    for ii,m in enumerate(max_):
        if m>=xh[i][0]:
            value -= a * c[ii]
    #print(xh[i][0],value)
    temp = max(0,-(-value//a))
    ans += temp
    c.append(temp)
    max_.append(xh[i][0]+2*d)
print(ans)

### FIXED CODE ###

import sys
from bisect import bisect
 
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size
 
	def Get(self, i):#iを返す
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s
 
	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return
 
	def SegAdd(self, l, r, x):#lからrにxを足す
		self.PointAdd(l, x)
		self.PointAdd(r+1, -x)
		return
 
 
n, d, a = map(int, input().split())
d *= 2
mo = sorted([list(map(int, input().split())) for _ in range(n)])
for i in range(n):
	mo[i][1] = (mo[i][1]-1)//a + 1
reach = []
moo = [x[0] for x in mo]
mooo = [x[1] for x in mo]
for x in moo:
	reach.append(bisect(moo, x+d)-1)
#print(reach)
 
bit = BIT(n)
 
ans = 0
for i, h in enumerate(mooo):
	gap = max(0, h - bit.Get(i+1))
	bit.SegAdd(i+1, reach[i]+1, gap)
	ans += gap
 
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for  _ in range(n)]
for i in range(n):
    print(max(a[i+1:]+a[:i]))

### FIXED CODE ###

n=int(input())
a=[int(input()) for  _ in range(n)]
b=sorted(a,reverse=True)
max0=b[0]
max1=b[1]
for i in range(n):
    if a[i]!=max0:
        print(max0)
    else:
        print(max1)
### BUGGY CODE ###

N = int(input())
S = [[] for i in range(10)]
count = 0
flag = 0
for i in range(N):
  string = input()
  for s in S[len(string)-1]:
    if string == s:
      flag = 1
      break
  if flag == 0:
    S[len(string)-1].append(string)
    count += 1
  flag = 0
print(count)

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
  string = input()
  S.append(string)
S = sorted(S)
count = N
for i in range(N-1):
  if S[i] == S[i+1]:
    count -= 1
print(count)
### BUGGY CODE ###

import math
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
for i in range(m):
  c=math.floor(a[-1]/2)
  a[-1]=c
  a.sort()
 
sum=0
for i in range(n):
  sum+=a[i]
  
print(sum)
  


### FIXED CODE ###

from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
A = [-1*int(i) for i in input().split()]
heapify(A)

for i in range(M):
    n = -1 * heappop(A)
    heappush(A, -1*(n//2))

print(-1*sum(A))
### BUGGY CODE ###

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

_mod = 10 ** 9 + 7

ans = 0

for i in range(k, n + 2):
    min0 = sum(range(0,i))
    max0 = sum(range(n + 1 - i, n + 1))
        
    tota0 = max0 - min0 + 1
    ans += tota0 % _mod

print(ans % _mod)

### FIXED CODE ###

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

_mod = 10 ** 9 + 7

ans = 0

#init
min0 = sum(range(0,k))
max0 = sum(range(n + 1 - k, n + 1))
cnt = max0 - min0 + 1
ans = cnt

for i in range(k+1 , n + 2):
#    min0 = min0 + i - 1
#    max0 = max0 + (n + 1 - i)
#    cnt  = max0 + (n + 1 - i) - (min0 + i - 1) + 1
    cnt = cnt + (n + 1 - i) - (i - 1)    
    ans += cnt % _mod

print(ans % _mod)
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()

positions = []
for i in range(len(S)-1):
    if S[i] == 'A':
        if S[i+1] == 'C':
            positions.append(i)
            i+=1

for i in range(Q):
  L, R = map(int,input().split())
  c = 0
  for p in positions:
    if L-1 <= p and R-1 >= p+1:
        c+=1
  print(c)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6 + 7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

K = int(input())
S = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += (cmb(i+n-1, n-1, mod) * pow(25, i) * pow(26, (K-i))) % mod
print(ans%mod)

### FIXED CODE ###

# F - Strivore
import sys
MOD = 10**9+7
K = int(input())
S = input()
l = len(S)
ans = 0
 
tmp = pow(26,K,MOD)
ans = tmp
waru = pow(26,-1,MOD)
 
for i in range(1,K+1):
    tmp = (tmp*25*waru)%MOD
    tmp = (tmp*(l-1+i)*pow(i,-1,MOD))%MOD
    ans = (ans+tmp)%MOD
 
print(ans)