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

n, m = map(int, input().split())
ab = []
for _ in range(n):
    ab.append(list(map(int, input().split())))
ab.sort(key=lambda x:x[1], reverse=True)
ans = 0
for i in range(1, m+1):
    for j in range(len(ab)):
        if ab[j][0] <= i:
            res = ab.pop(j)
            ans += res[1]
            break
print(ans)

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
ab = [[] for _ in range(m)]
for _ in range(n):
    a, b = map(int, input().split())
    if m >= a:
        ab[a-1].append(-b)
heap = []
ans = 0
for i in range(m):
    for j in ab[i]:
        heapq.heappush(heap, j)
    if heap:
        res = heapq.heappop(heap)
        ans += -res
print(ans)
### BUGGY CODE ###

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

sum=0
for i in range(n):
    if(a[i]>x):
        temp=a[i]-x
        a[i]-=temp
        sum+=temp
    if(i>0):
        while(x<a[i]+a[i-1]):
            a[i]-=1
            sum+=1
print(sum)

### FIXED CODE ###

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

sum=0
for i in range(n):
    if(a[i]>x):
        temp=a[i]-x
        a[i]-=temp
        sum+=temp
    if(i>0):
        temp=a[i]+a[i-1]
        if(x<temp):
            a[i]-=temp-x
            sum+=temp-x
print(sum)
### BUGGY CODE ###

n = int(input())
s = list(input())
res = []

for i in range(n):
    res += [s[:i].count("W") + s[i+1:].count("E")]

print(min(res))


### FIXED CODE ###

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

num_eas = s.count('E')


res = []
res += [num_eas - s[0].count("E")]

for i in range(1,n):
    res += [res[i-1] + s[i-1].count("W") - s[i].count("E")]
    
print(min(res))
### BUGGY CODE ###

import sys

input=sys.stdin.readline

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

m=int((M+2)**.5)
isu=[0]*(M+2)
isudata=[0]*((M+1)//m+1)
RMQdata=[0]*((M+1)//m+1)

def update(l,r,x):
    id=l
    while id<=r:
        L=id
        q=id//m
        R=min(m*(q+1)-1,r)
        if R-L+1==m:
            isudata[q]+=x
            RMQdata[q]+=x
        else:
            for i in range(L,R+1):
                isu[i]+=x
            res=2**31
            for i in range(m*q,min(M+2,m*(q+1))):
                test=isu[i]+isudata[q]
                res=min(res,test)
            RMQdata[q]=res
        id=R+1

def query(l,r):
    id=l
    res=2**31
    while id<=r:
        L=id
        q=id//m
        R=min(m*(q+1)-1,r)
        if R-L+1==m:
            res=min(res,RMQdata[q])
        else:
            for i in range(L,R+1):
                test=isu[i]+isudata[q]
                res=min(res,test)
        id=R+1

    return res

for i in range(1,M+1):
    update(0,i,1)

add=M-N
hito=[]
for i in range(N):
    L,R=map(int,input().split())
    hito.append((L,R))
hito.sort()

for l,r in hito:
    update(0,r,-1)
    t=query(l+1,M+1)+l
    add=min(t,add)

print(max(-add,0))

### FIXED CODE ###

import sys

input=sys.stdin.readline

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

# N: 処理する区間の長さ
INF = 2**31-1

LV = (M+2-1).bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x):
    *ids, = gindex(l, r)
    propagates(*ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[i-1] = min(data[2*i-1], data[2*i])

# 区間[l, r)内の最小値を求める
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r

    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for i in range(1,M+1):
    update(0,i+1,1)

add=M-N
hito=[]
for i in range(N):
    L,R=map(int,input().split())
    hito.append((L,R))
hito.sort()
#test=[query(i,i+1) for i in range(M+2)]
#print(test)
for l,r in hito:
    update(0,r+1,-1)
    #test=[query(i,i+1) for i in range(M+2)]
    #print(test)
    m=query(l+1,M+2)+l
    add=min(m,add)

print(max(-add,0))
### BUGGY CODE ###

from bisect import bisect_left

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

if X*Y*Z <= 10**10:
  D = sorted([A[i]+B[j]+C[k] for i in range(X) for j in range(Y) for k in range(Z)],reverse=True)
  for i in range(K):
    print(D[i])
  
else:
  A = sorted(A)
  D = sorted([B[i]+C[j] for i in range(Y) for j in range(Z)])

  thr = K
  s = A[-1]+D[max(0,len(D)-thr)]
  prev_idx=0
  selected = [A[-1] + D[i] for i in range(len(D))]
  for i in range(1,X):
    r = s - A[-1-i]
    if r<=0:break
    idx = bisect_left(D,r,prev_idx,len(D)-1)
    if idx == len(D):break
    selected.extend([A[-1-i] + D[j] for j in range(idx,len(D))])
    prec_idx = idx

  selected = sorted(selected,reverse=True)
  print(len(selected))

  for i in range(K):
    print(selected[i])

### FIXED CODE ###

from bisect import bisect_left

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

if X*Y*Z <= 50000:
  D = sorted([A[i]+B[j]+C[k] for i in range(X) for j in range(Y) for k in range(Z)],reverse=True)
  for i in range(K):
    print(D[i])
  
else:
  A = sorted(A)
  D = sorted([B[i]+C[j] for i in range(Y) for j in range(Z)])

  thr = K
  s = A[-1]+D[max(0,len(D)-thr)]
  prev_idx=0
  selected = [A[-1] + D[i] for i in range(max(0,len(D)-thr),len(D))]
  
  for i in range(1,X):
    r = s - A[-1-i]
    if r<=0:break
    idx = bisect_left(D,r,prev_idx,len(D)-1)
    if idx == len(D):break
    selected.extend([A[-1-i] + D[j] for j in range(idx,len(D))])
    prec_idx = idx

  selected = sorted(selected,reverse=True)

  for i in range(K):
    print(selected[i])
### BUGGY CODE ###

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

def dijkstra_heap(s,edge,n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

def main():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]
    U = set()
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        U.add(u)
        edge[u].append(v)

    S, T = map(int, input().split())
    S -= 1
    T -= 1
    search = [False] * N
    can = [[] for _ in range(N)]
    def dfs(s,p,d):
        if d == 3:
            can[s].append((1,p))
            search[s] = True
            return
        for e in edge[p]:
            dfs(s,e,d+1)

        return

    for u in U:
        if search[u]:
            continue
        dfs(u,u,0)
    d = dijkstra_heap(S,can,N)
    if d[T] == 10**20:
        print(-1)
    else:
        print(d[T])




if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    edge = [[] for _ in range(N)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)

    S, T = map(int, input().split())
    S -= 1
    T -= 1
    dist = [[float('inf')] * 3 for _ in range(N)]
    dist[S][0] = 0
    q = deque([])
    q.append((S,0))
    while q:
        v, l = q.popleft()
        nl = (l + 1) % 3
        for nv in edge[v]:
            if dist[nv][nl] != float('inf'):
                continue
            dist[nv][nl] = dist[v][l] + 1
            q.append((nv,nl))
        
    
    if dist[T][0] == float('inf'):
        print(-1)
    else:
        print(dist[T][0] // 3)




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

import math
k = int(input())

ans = 0
for p in range(1, k+1):
    for q in range(1, k+1):
        for r in range(1, k+1):
            ans += math.gcd(math.gcd(p, q), r)

print(ans)

### FIXED CODE ###

import math
k = int(input())

ans = 0
for p in range(1, k+1):
    for q in range(1, k+1):
        for r in range(1, k+1):
            ans += math.gcd(math.gcd(p, q), r)

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

N = int(input())
A = list(map(int,input().split()))
from bisect import bisect_left

Ans = 0
pans = 0
low,high = -(10**5),10**9
for i in range(120):
    anslow,anshigh = 0,0
    for i in range(N):
        anslow += abs(A[i]-(i+low))
        anshigh += abs(A[i]-(i+high))
    if anshigh > anslow:
        high=(high+low)//2
    else:
        low=(high+low)//2
    Ans = min(anshigh,anslow)

print(Ans)

### FIXED CODE ###

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

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

A.sort()

Ans = 0
mi = len(A)//2 # 中央値のindex
for i in range(N):
    Ans += abs(A[i]-A[mi])

print(Ans)
### BUGGY CODE ###

s = list(input())
q = int(input())

for i in range(q):
    tfc = input().split()
    if len(tfc) == 1:
        t = tfc[0]
    else:
        t, f, c = tfc
    if t == '1':
        s.reverse()
    elif t == '2':
        if f == '1':
            s[0:0] = c
        elif f == '2':
            s.append(c)

print("".join(s))


### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
rev_f = True

for i in range(q):
    cmd = input().split()
    if cmd[0] == '1':
        rev_f = (False if rev_f else True)
    else:
        f = cmd[1]
        c = cmd[2]
        if (rev_f and f == '1') or (not rev_f and f != '1'):
            s.appendleft(c)
        else:
            s.append(c)

print(''.join(s if rev_f else reversed(s)))
### BUGGY CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint

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

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

room_next = [[] for n in range(N)]

for a, b in zip(A, B):
    room_next[a - 1].append(b - 1)
    room_next[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []

while stack:
    # print('visited', visited)
    # print('next', stack)
    now = stack.pop()
    if now not in visited:
        visited.append(now)
        for r in room_next[now]:
            if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
                room_depth[r] = room_depth[now] + 1
                room_sign[r] = now + 1

                if r not in visited:
                    stack.append(r)

print('Yes')
for s in room_sign[1:]:
    print(s)

### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

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

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1

""" Input
N = int(input())
N, A, B = map(int, input().split())
A = list(map(int, input().split()))
A = np.array(input().split(), dtype=np.float64)
D = [int(input()) for _ in range(N)]
AB = [[int(x) for x in input().split()] for _ in range(N)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
"""

S = input().rstrip()

counter = 0
for l_index in range(len(S) - 4):
    atama = int(S[l_index:l_index+2])
    if atama % 2 != 0:
        continue
    else:
        r_index = 5
        top = l_index
        while True:
            saigo = l_index + r_index
            if saigo > len(S):
                break
            kouho = int(S[top:saigo])
            if kouho % 2019 == 0:
                counter += 1
                top = r_index
                r_index += 5
                continue
            r_index += 1


print(counter)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1
MOD = 2019

"""
gcd(10, 2019) = 1 互いに素
-> 10のmod2019での逆元(1/10)が存在
"""
S = input().rstrip()
s_list = list(map(int, list(S)))[::-1]

counts = [0] * MOD
counts[0] = 1

num, d = 0, 1

for s_element in s_list:
    num += s_element * d
    num %= MOD
    d *= 10
    d %= MOD
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

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

[K, S] = list(map(int, input().split()))
count = 0
total = 0
for X in range(K+1):
  if X > S:
    break
  for Y in range(K+1):
    sub = X + Y
    if S < sub and sub < (2/3) * S:
      break
    Z = S - X - Y
    if 0 <= Z and Z <= K:
      count +=1
      
print(count)

### FIXED CODE ###

[K, S] = list(map(int, input().split()))
count = 0
for X in range(K+1):
  for Y in range(K+1):
    Z = S - X - Y
    if 0 <= Z and Z <= K:
      count +=1

print(count)
### BUGGY CODE ###

K = int(input())
ans = -1
if K in [2,5]:
    pass
else:
    num = 7
    ans = 0
    while True:
        ans += 1
        if num % K == 0:
            break
        else:
            num = num * 10 + 7
print(ans)

### FIXED CODE ###

K = int(input())
ans = -1
if K%2 == 0:
    pass
elif K%5 == 0:
    pass
else:
    num = 7
    ans = 0
    while True:
        ans += 1
        if num % K == 0:
            break
        else:
            num = (num * 10 + 7)%K
print(ans)
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7




pair_flg=0
set_flg=0
n=I()
A=LI()
t_set=set()
s_set=set(range(2,n+1))
D=defaultdict(set)

for j in range(n):
    a=A[j]
    prime_set = D[A[j]]
    flg=0
    if not prime_set:
        for i in range(2, int(a ** 0.5) + 1):
            while a % i == 0:
                prime_set.add(i)
                a //= i
                if D[a]:
                    prime_set|=D[a]
                    flg=1
                    break
            if a == 1 or flg:
                break
        if a != 1:
            prime_set.add(a)
        D[A[j]]=prime_set
    if prime_set&t_set:
        pair_flg=1
    t_set|=prime_set
    s_set&=prime_set


if not pair_flg:
    print("pairwise coprime")
elif not s_set:
    print("setwise coprime")
else:
    print("not coprime")




### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

n=I()
A=LI()
l=A[0]
num=[0]*(10**6+1)
for i in range(1,n):
    num[A[i]]+=1
    l=gcd(l,A[i])



if l!=1:
    print("not coprime")
    exit()


for j in range(2,10**6):
    ret=0
    for k in range(j,10**6+1,j):
        ret+=num[k]
    if ret>1:
        print("setwise coprime")
        exit()

print("pairwise coprime")
### BUGGY CODE ###

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

for i in range(1, n+1):
    print(l.count(i))

### FIXED CODE ###

from collections import Counter

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

d = Counter(l)
for i in range(1, n+1):
    print(d[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def InMap(): return list(map(int, input().split(' ')))
def In(): return int(input())
def InS(): return input()

N, K = InMap()
P = InMap()
print((max([sum(P[i:i+K]) for i in range(N - K + 1)]) + K) / 2)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def InMap(): return list(map(int, input().split(' ')))
def In(): return int(input())
def InS(): return input()

N, K = InMap()
P = InMap()

Res = [0]*(N - K + 1)
tmp = sum(P[0:K])
for i in range(K, N):
    Res[i-K] = tmp
    tmp -= P[i-K]
    tmp += P[i]
Res[-1] = tmp
print((max(Res) + K) / 2)
### BUGGY CODE ###

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

answer = 0
for i in range(N):
    if min(Ps[:i + 1]) >= Ps[i]:
        answer = answer + 1

print(answer)

### FIXED CODE ###

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

answer = 0
min_num = 2 * 10 ** 5 + 1
for p in Ps:
    min_num = min(p, min_num)
    if min_num >= p:
        answer = answer + 1

print(answer)
### BUGGY CODE ###

n=int(input())

total=0

for i in range(n):
  #print(f'i+1={i+1}')
  j=i
  while j<n:
    #print(f'j+1={j+1}')
    k=j
    while k<n:
      #print(f'k+1={k+1}')
      kouho=min(i+1,j+1,k+1)
      while True:
        #kouhoが最大公約数の時
        if (i+1)%kouho==0 and (j+1)%kouho==0 and (k+1)%kouho==0:
          #３つとも同じ数字
          if i==j and j==k:
            total+=kouho
          #２つのみ同じ数字
          elif i==j or j==k or k==i:
            total+=kouho*3
          #同じ数字がない時
          else:
            total+=kouho*6
          break
        else:
          kouho -= 1
      k+=1
    j+=1
          
print(total)

### FIXED CODE ###

n=int(input())

total=0

for i in range(n):
  #print(f'i+1={i+1}')
  j=i
  while j<n:
    #print(f'j+1={j+1}')
    k=j
    while k<n:
      #print(f'k+1={k+1}')
      kouho=min(i+1,j+1,k+1)
      while True:
        #kouhoが最大公約数の時
        if (i+1)%kouho==0 and (j+1)%kouho==0 and (k+1)%kouho==0:
          #３つとも同じ数字
          if i==j and j==k:
            total+=kouho
          #２つのみ同じ数字
          elif i==j or j==k or k==i:
            total+=kouho*3
          #同じ数字がない時
          else:
            total+=kouho*6
          break
        else:
          kouho -= 1
      k+=1
    j+=1
          
print(total)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
C = {}
for _ in range(N):
    A,B = map(int, input().split())
    if A in C:
        C[A].append(B)
    else:
        C[A] = []
        C[A].append(B)
for i in C:
    C[i] = sorted(C[i])[::-1]

answer = 0
tmp = deque()

for i in range(M+1):
    if i in C:
        tmp2 = tmp
        tmp = deque()
        right = deque(C[i])
        while len(tmp2) != 0 and len(right) != 0:   # line7
            if tmp2[0] > right[0]:                  # line8
                tmp.append(tmp2.popleft())           # line9
            else:                                   # line10
                tmp.append(right.popleft())          # line11
        if len(tmp2) != 0:                          # line12
            tmp+=tmp2                      # line13
        elif len(right) != 0:                       # line14
            tmp+=right
    if tmp != deque():
        answer += tmp[0]
        tmp.popleft()
print(answer)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
C = {}
for _ in range(N):
    A,B = map(int, input().split())
    if A in C:
        C[A].append(B)
    else:
        C[A] = []
        C[A].append(B)
for i in C:
    C[i] = sorted(C[i])[::-1]

answer = 0
tmp = []
heapq.heapify(tmp)

for i in range(M+1):
    if i in C:
        right = C[i]
        for j in right:
            heapq.heappush(tmp,-1*j)
        
    if tmp != []:
        answer += -1*heapq.heappop(tmp)
print(answer)
### BUGGY CODE ###



class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

n,k = map(int,input().split())
seg = SegTree(300001)
# a = [0]*n
# seg.build(a)
for i in range(n):
    a = int(input())
    seg.set_val(a,seg.fold(max(0,a-k),min(300001,a+k+1)) + 1)

print(seg.fold(0,300001))

### FIXED CODE ###



class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

n,k = map(int,input().split())
seg = SegTree(300001)
# a = [0]*n
# seg.build(a)
for i in range(n):
    a = int(input())
    seg.set_val(a,seg.fold(max(0,a-k),min(300001,a+k+1)) + 1)

print(seg.fold(0,300001))