Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline
 
from numba import njit
import numpy as np
@njit('i8,i8,i8[::1]',cache=True)
def resolve():
    N, K = map(int, inp().split())
    A = np.array(list(map(int, inp().split())), np.int64)
 
    for _ in range(K):
        imos_table = np.zeros(N + 1, np.int64)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = np.cumsum(imos_table)[:-1]
        if np.all(A == N):
            print(*A)
            return
    else:
        print(*A)
        
if __name__ == "__main__":
    resolve()

### FIXED CODE ###


from itertools import accumulate
def resolve():

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

    for _ in range(K):
        imos_table = [0]*(N+1)
        for i, a in enumerate(A):
            # 配列の個数を超えないように注意
            imos_table[max(i - a, 0)] += 1
            imos_table[min(i + a + 1, N)] -= 1
        A = list(accumulate(imos_table))[:-1]
        if all([True if a == N else False for a in A]):
            print(*A)
            return
    else:
        print(*A)

if __name__ == "__main__":
    resolve()
a=list(map(int,input().split()))
print(a0*a1/2)

### FIXED CODE ###

a=list(map(int,input().split()))
print('{:.0f}'.format(a[0]*a[1]/2))
n,m=input().split()
n=int(n)
m=int(m)
li=[int(k) for k in input().split()]
dp=[0]*n
dp[0]=0
dp[1]=li[1]-li[0]
for i in range(2,n):
  ans=10**9
  for j in range(1,m+1):
    if i-j<0:
      break
    ans=min(ans,abs(li[i]-li[i-j])+dp[i-j])
  dp[i]=ans
print(dp[n-1])  


### FIXED CODE ###

n=int(input())
li=[int(k) for k in input().split()]
dp=[0]*(n)
dp[0]=0
dp[1]=abs(li[1]-li[0])

for i in range(2,n):
  dp[i]=min(abs(li[i]-li[i-1])+dp[i-1],abs(li[i]-li[i-2])+dp[i-2])
#print(dp)
print(dp[n-1])
# def gcd(n,m):
#     if m == 0:
#         return n
#     else:
#         x = max(n,m)%min(n,m)
#         while x != 0:
#             return gcd(m,x)
#         else:
#             return m

import math
import copy

l = list(map(int,input().split()))
A = l[0]
B = l[1]
C = l[2]
D = l[3]

E = C * D //math.gcd(C,D)

f = B//C - (A-1)//C
f = f+(B//D - (A-1)//D)
ans = B-A+1-f + B//E-(A-1)//E
print(ans)


### FIXED CODE ###

from fractions import gcd 

l = list(map(int,input().split()))
A = l[0]
B = l[1]
C = l[2]
D = l[3]

E = C * D //gcd(C,D)

f = B//C - (A-1)//C
f = f+(B//D - (A-1)//D)
ans = B-A+1-f + B//E-(A-1)//E
print(ans)
import fraction
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fraction.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

LCM = lcm_list(A)
ans = 0

for i in range(N):
    ans+=LCM//A[i]
print(ans%mod)

### FIXED CODE ###

import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

LCM = lcm_list(A)
ans = 0

for i in range(N):
    ans+=LCM//A[i]
print(ans%mod)
S = input()
K = int(input())

SK = S*K
buf=''
cnt = 1
total = 0
cnts = []
for s in SK:
    #print(buf,s,cnt)
    if s == buf:
        cnt += 1       
    else:
        cnts.append(cnt)
        total += int(cnt/2)
        cnt = 1        
    buf = s
cnts.append(cnt)    
total += int(cnt/2)

print(total)

### FIXED CODE ###

from itertools import groupby
S = input()
K = int(input())
a = [len(tuple(s)) for _, s in groupby(S)]
ans = 0
 
if S[0] == S[-1] and K > 1:
    if len(a) == 1:
        ans = a[0]*K // 2
    else:
        ans = a[0] // 2 + a[-1] // 2 + (a[0]+a[-1]) // 2 * (K-1)
        ans += sum(n // 2 for n in a[1:-1]) * K
else:
    ans = sum(n // 2 for n in a) * K
print(ans)
n=int(input())
d={2:0}
while n%2<1:  n//=2;  d[2]+=1
for i in range(3,int(n**0.5)+1,2):
  while n%i<1:  n//=i;  d[i]=d.get(i,0)+1
  if n<2: break
if n>1: d[x]=1
a=0
for i in d.values():
  t=c=0
  while t+c<i: c+=1; t+=c
  a+=c
print(a)

### FIXED CODE ###

n=int(input())
if n==1: print(0); exit()
M=10**6+1
l=[]
p=[1]*M
p[0]=p[1]=0
for i in range(2,M):
  if p[i]:
    l.append(i)
    for j in range(2*i,M,i):
      p[j]=0
d={}
for k in l:
  c=0
  while n%k==0: n//=k; c+=1
  if c>0: d[k]=c
s=[1]
for i in range(2,9):
  s.append(s[-1]+i)
a=0
for i in d.values():
  for j in s:
    if j>i: break
    a+=1
print(a+(n>1))
t=int(input())
a=[2,4,5,7,9]
x=n%10
if x in a:
  print("hon")
elif x==3:
  print("bon")
else:
  print("pon")

### FIXED CODE ###

n=int(input())
a=[2,4,5,7,9]
x=n%10
if x in a:
  print("hon")
elif x==3:
  print("bon")
else:
  print("pon")
from collections import deque

def dfs(v, P, visited, N):
    if len(list(filter(lambda x: x == True, visited))) == N:
        return 1

    c = 0
    for i in P[v]:
        if visited[i]: continue
        visited[i] = True
        c += dfs(i, P, visited, N)
        visited[i] = False

    return c

def resolve():
    N, M = map(int, input().split())
    P = [[] for _ in range(N)]
    for i in range(N):
        pp, ss = map(int, input().split())
        P[pp-1].append(ss-1)
        P[ss-1].append(pp-1)

    visited = [False] * N
    visited[0] = True

    print(dfs(0, P, visited, N))

resolve()

### FIXED CODE ###

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

visited = [False] * N
visited[0] = True
d = {}
for a, b in A:
    d.setdefault(b-1, []).append(a-1)
    d.setdefault(a-1, []).append(b-1)

l = sorted(d.items())

def dfs(v, seen):
    if False not in seen: return 1
    
    c = 0
    for i in d[v]:
        if (seen[i]): continue
        seen[i] = True
        c += dfs(i, seen)
        seen[i] = False
    return c
    
print(dfs(0, visited))
n = int(input())

g = [[] for _ in range(n)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u - 1].append((v - 1, w))
    g[v - 1].append((u - 1, w))

color = [-1] * n
dist = [0] * n

import queue
def dfs(v):
    color[v] = dist[v] % 2
    for next_v in g[v]:
        if color[next_v[0]] == -1 and next_v[1] != 0:
            dist[next_v[0]] = dist[v] + next_v[1]
            dfs(next_v[0])

# 0を始点として各点までの距離を求める
dfs(0)

for c in color:
    print(c)

### FIXED CODE ###

n = int(input())

g = [[] for _ in range(n)]
for i in range(n - 1):
    u, v, w = map(int, input().split())
    g[u - 1].append((v - 1, w))
    g[v - 1].append((u - 1, w))

color = [-1] * n
dist = [0] * n

import queue
def dfs(v):
    color[v] = dist[v] % 2
    q = queue.LifoQueue()
    q.put(v)

    while not q.empty():
        vv = q.get()
        for next_v in g[vv]:
            if color[next_v[0]] == -1 and next_v[1] != 0:
                dist[next_v[0]] = dist[vv] + next_v[1]
                color[next_v[0]] = dist[next_v[0]] % 2
                q.put(next_v[0])

# 0を始点として各点までの距離を求める
dfs(0)

for c in color:
    print(c)
while 1:
    t,n = map(int,raw_input().split())
    if t == n == 0: break
    block = [map(int,raw_input().split()) for _ in range(n)]
    sx,sy = map(int,raw_input().split())
    visited = []
    visited.append([sx,sy])
    que = [[sx,sy,t]]
    ans = 1
    while que:
        x,y,tt = que.pop(0)
        if tt == 0: continue
        for dx,dy in zip([1,1,0,-1,-1,0],[0,1,1,0,-1,-1]):
            nx,ny = x+dx,y+dy
            if [nx,ny] not in visited and [nx,ny] not in block:
                que.append([nx,ny,tt-1])
                visited.append([nx,ny])
                ans += 1
    print ans

### FIXED CODE ###

while 1:
    t,n = map(int,raw_input().split())
    if t == n == 0: break
    block = []
    for loop in range(n):
        x,y = map(int,raw_input().split())
        block.append((x+100,y+100))
    sx,sy = map(int,raw_input().split())
    sx += 100; sy += 100
    visited = [[False]*200 for _ in range(200)]
    visited[sy][sx] = True
    que = [[sx,sy,t]]
    ans = 1
    while que:
        x,y,tt = que.pop(0)
        if tt == 0: continue
        for dx,dy in zip([1,1,0,-1,-1,0],[0,1,1,0,-1,-1]):
            nx,ny = x+dx,y+dy
            if not visited[ny][nx] and (nx,ny) not in block:
                que.append([nx,ny,tt-1])
                visited[ny][nx] = True
                ans += 1
    print ans
BIG_NUM = 10**18

N, K = map(int, input().split(" "))
H = list(map(int, input().split(" ")))

l = [BIG_NUM]*(N+200)
l[0] = 0
for i in range(1, N):
    l[i] = min([l[i-j] + abs(H[i]-H[i-j]) for j in range(1, K+1)])

# print(l)
print(l[N-1])

### FIXED CODE ###

N, K = map(int, input().split(" "))
H = list(map(int, input().split(" ")))

costs = [0]*(N+10)
for i in range(1, N):
    j = max(0, i-K)
    h_i = H[i]
    costs[i] = min(cost+abs(h_i-h) for cost, h in zip(costs[j:i], H[j:i]))

print(costs[N-1])
import math
a,b,x = map(int,input().split())
if x > ((a**2)*b)/2:
    print(math.degrees(math.atan((2*(b-x/(a**2))/a)))
else:
    print(math.degrees(math.atan((a*(b**2))/(2*x))))

### FIXED CODE ###

import math
a,b,x = map(int,input().split())
if x > ((a**2)*b)/2:
    print(math.degrees(math.atan((2*(b-x/(a**2))/a))))
else:
    print(math.degrees(math.atan((a*(b**2))/(2*x))))
from itertools import product


def main():
    """
    2^20 = 1,048,576
    q = 200
    200,000,000
    limit 5s ???????????????OK
    """
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    M = map(int, input().split())

    for m in M:
        if m == 0 or solve(m, A, n):
            print("yes")
        else:
            print("no")


def solve(m, A, n):
    # for b in f1(n):
    for b in product([0, 1], repeat=n):
        s = sum(a * bit for a, bit in zip(A, b))
        if m == s:
            return True

    return False


def f1(n):
    for i in range(2 ** n):
        # 0/1???n??????????????????bit????????¨
        # 0b ?????????
        bit = bin(i)[2:]
        yield map(int, bit.zfill(n))

if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import product


def main():
    """
    2^20 = 1,048,576
    q = 200
    200,000,000
    limit 5s ???????????????OK
    """
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    M = map(int, input().split())

    dp(n, A, q, M)


def combination(n, A, q, M):
    for m in M:
        if m == 0 or solve(m, A, n):
            print("yes")
        else:
            print("no")


def dp(n, A, q, M):
    M_max = 2000
    _dp = [False] * (M_max + 1)
    for a in A:
        # ?°??????????????????????????????¨????????????????????±?????????(a???2????¶?????????¨?????????)
        for i in range(M_max, 0, -1):
            if _dp[i] and i + a <= M_max:
                _dp[i + a] = True
        # ???????¨????????????¨????????°?????¨????¨±????????????????????¨??§
        _dp[a] = True

    for m in M:
        if _dp[m]:
            print("yes")
        else:
            print("no")


def solve(m, A, n):
    # for b in f1(n):
    for b in product([0, 1], repeat=n):
        s = sum(a * bit for a, bit in zip(A, b))
        if m == s:
            return True

    return False


def f1(n):
    for i in range(2 ** n):
        # 0/1???n??????????????????bit????????¨
        # 0b ?????????
        bit = bin(i)[2:]
        yield map(int, bit.zfill(n))

if __name__ == '__main__':
    main()
import sys
#import copy
import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.buffer.read

def main():
    # input
    N = int(readline())
    #S = np.array(list(readline()))
    S = np.array(list(read().rstrip()), np.int8)
    #print(S)

    R = np.sum(S == ord('R'))
    G = np.sum(S == ord('G'))
    B = np.sum(S == ord('B'))

    ans = R*G*B

    for i in range(N-2):
        for j in range(i+1, N-1):
            k = 2 * j - i
            if k >= N:
                break
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                ans -= 1

    print(ans)
    #print('end')


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
#import copy
#import numpy as np
#import itertools
import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read
count = collections.Counter

def main():
    N = int(readline())
    S = input()

    values = list(count(S).values())
    if len(values) < 3:
        print(0)
        return
    
    ans = values[0] * values[1] * values[2]

    for i in range(N-2):
        for j in range(i+1, N-1):
            k = 2 * j - i
            if k >= N:
                break
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                ans -= 1

    print(ans)
    #print('end')


if __name__ == "__main__":
    main()
def check(a,cnt):
  b = [int(x)%2 for x in a]
  if 1 in b:
    return 0,cnt
  else :
    cnt +=1
    b = [int(x)/2 for x in a]
    return 1,cnt
 
N = input()
a = input().split()
cnt = 0
while(1):
  m,cnt = check(a,cnt)
  if m == 0:
    print(cnt)
  else :
    continue

### FIXED CODE ###

s=input()
a=[int(x) for x in s]
print(sum(a))
s=raw_input()
n=len(s)
cnt=[[0]*26 for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(26):
        cnt[i+1][j]=cnt[i][j]
    cnt[i+1][ord(s[i])-ord("a")]+=1
if n==2:
    if s[0]==s[1]:
        print 1,2
        quit()
    else:
        print -1,-1
        quit()
for i in xrange(n):
    for j in xrange(i+3,n+1):
        max_cnt=0
        for k in xrange(26):
            max_cnt=max(max_cnt,cnt[j][k]-cnt[i][k])
        if (j-i)/2<max_cnt:
            print i+1,j
            quit()
print -1,-1

### FIXED CODE ###

n=input()
a=map(int,raw_input().split())
ans=10**9
for j in xrange(-100,101):
    asum=0
    for i in xrange(n):
        asum+=(a[i]-j)**2
    ans=min(ans,asum)
print(ans)
import sys
input = sys.stdin.readline

N, W = map(int, input().split())
items = [list(map(int, input().split())) for i in range(N)]

dpt = [0] * (W+1)

for w, v in items:
    for j in range(W, w-1, -1):
        a = dpt[j]
        b = dpt[j-w]+v
        if a > b:
            dpt[j] = a
        else:
            dpt[j] = b

print(dpt[W])


### FIXED CODE ###

import math
N = int(input())
step_list = list(map(int, input().split()))

dp_table = [math.inf] * N
dp_table[0] = 0

for i in range(1, N):
    if i <= 1:
        dp_table[i] = dp_table[i-1] + abs(step_list[i-1] - step_list[i])
    else:
        dp_table[i] = min(dp_table[i-1] + abs(step_list[i-1] - step_list[i]),
                          dp_table[i-2] + abs(step_list[i-2] - step_list[i]))

print(dp_table[N-1])
import math , sys

N  = int( input() )

A = list(map(int, input().split() ) )
M = max( [ i + A[i] for i in range(N) ])
B = [0] * (2*M)
ans = 0
for i in range(N):
    if i - A[i] >=0:
        ans += B[i - A[i]]
    B[i + A[i]]+=1
print(ans)

### FIXED CODE ###

import math , sys

N  = int( input() )

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

def Prime(x):
    ub=int(math.sqrt(x))+2
    if x==2 or x==3 or x==5 or x==7:
        return True
    for i in range(2,ub):
        if x%i==0:
            return False
    return True

y = N
while not Prime(y):
    y+=1

def h1(x):
    return x % y
def h2(x):
    return 1+ x%(y-1)
def h(x,i):
    return (h1(x) + i*h2(x)) % y

def insert(T,x):
    i=0
    while True:
        j=h(x,i)
        if T[j][0]== -1:
            T[j][0]=x
            T[j][1]=1
            return j
        elif x ==T[j][0]:
            T[j][1]+=1
            return j
        else:
            i+=1

def search(T,x):
    i=0
    while True:
        j=h(x,i)
        if T[j][0] == x:
            return T[j][1]
        elif T[j][0] == -1:
            return -1
        else:
            i+=1

T = [[-1,0] for _ in range(y)]
for i in range(N):
    insert(T , i + A[i])
ans =0
        
for j in range(N):
    if j - A[j]>=0:
        s = search(T, j - A[j])
        if s >=0:
            ans+=s
print(ans)
from collections import defaultdict


def get_prime_factors(x):
    out = set()
    if x < 1:
        return out
    while not x%2:
        out.add(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.add(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.add(x)
    return out


def main():
    n = int(input())
    a = list(map(int, input().split()))
    df = defaultdict(lambda : 0)
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    val = max(df.values())
    if val == 1:
        print("pairwise coprime")
    elif val == n:
        print("not coprime")
    else:
        print("setwise coprime")

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict


def get_prime_factors(x):
    out = set()
    if x < 1:
        return out
    while not x%2:
        out.add(2)
        x //= 2
    i = 3
    while i*i <= x:
        if not x%i:
            out.add(i)
            x //= i
        else:
            i += 2
    if x != 1:
        out.add(x)
    return out


def main():
    n = int(input())
    a = list(map(int, input().split()))
    df = defaultdict(lambda : 0)
    for ai in a:
        primes = get_prime_factors(ai)
        for prime in primes:
            df[prime] += 1
    if df.values():
        val = max(df.values())
        if val == 1:
            print("pairwise coprime")
        elif val == n:
            print("not coprime")
        else:
            print("setwise coprime")
    else:
        print("pairwise coprime")

if __name__ == "__main__":
    main()
a,b=(int(x) for x in input().split())

if a==1 or b == 1:
  print("0")
else if a*b%2==0:
    print(int(a*b/2))
else:
    print(int((a*b-1)/2+1))

### FIXED CODE ###

x = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
N = int(input())
print(x[N-1])
N, M = map(int, input().split())
ac = [0] * N
wa = [0] * N

ac = 0
wa = 0

for i in range(M):
    p, S = input().split()
    p = int(p)

    if S == "AC":
        if ac[p-1] == 0:
            ac += 1
            
    else:
        if ac[N-1] == 0:
            wa += 1

print(ac, wa)


### FIXED CODE ###

C = input()
alphabet = "abcdefghijklmnopqrltuvwxyz"

for i in range(len(alphabet)):
    if alphabet[i] == C:
        print(alphabet[i+1])
        exit()
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, X = map(int, input().split())
a = list(map(int, input().split()))
l = [0]*(N+1)
for i in a:
    l[i] += 1
print(min[sum(l[0:X]), sum(l[X+1: N+1])])


### FIXED CODE ###

# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, X = map(int, input().split())
a = list(map(int, input().split()))
l = [0]*(N+1)
for i in a:
    l[i] += 1
print(min(sum(l[0:X]), sum(l[X+1: N+1])))
# coding: utf-8
n, m = [int(x) for x in input().split(" ")]
ans = 0
pen = 0
prbstate = {}
fins = {}
A = []
for i in range(m):
    A.append(input().split(" "))

for a in A:
    if a[1] == "AC":
        fins.setdefault(a[0], "AC")

for i in range(m):
    p, s = A[i]
    prbstate.setdefault(p, 0)
    if s == "AC":
        prbstate[p] = 1
    if s == "WA" and prbstate[p] == 0 and fins[p] == "AC":
        pen += 1
for x in prbstate.values():
    ans += x
print(ans, pen)

### FIXED CODE ###

# coding: utf-8
n, m = [int(x) for x in input().split(" ")]
ans = 0
pens = 0
prbstate = {}
fins = {}
A = []
for i in range(m):
    A.append(input().split(" "))
for a in A:
    if a[1] == "AC":
        fins.setdefault(a[0], 1)
for x in fins.values():
    ans += x
for i in range(m):
    p, s = A[i]
    prbstate.setdefault(p, 0)
    fins.setdefault(p, 0)
    if s == "AC":
        prbstate[p] += 1
    if s == "WA" and prbstate[p] < 1 and fins[p] == 1:
        pens += 1
print(ans, pens)
N = int(input())
for i in range(N, 1, -1):
    tmp = int(pow(i, 0.5))
    if tmp * tmp == i:
        break
print(i)


### FIXED CODE ###

N = int(input())
tmp = 1
for i in range(N, 1, -1):
    tmp = int(pow(i, 0.5))
    if tmp * tmp == i:
        break
print(tmp * tmp)
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
ab = []
for i in range(n):
    ab.append(na())

ab.sort(key=itemgetter(0))

pq = []
import  heapq

ans = 0
p = 0
for i in range(m+1):
    while p < n and ab[p][0] <= i:
        heapq.heappush(pq, -ab[p][1])
        p += 1

    if len(pq) == 0:
        continue

    ans -= heapq.heappop(pq)

print(ans)


### FIXED CODE ###

import sys
from operator import itemgetter

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m = na()
ab = []
for i in range(n):
    ab.append(na())

ab.sort(key=itemgetter(0))

pq = []
import  heapq

ans = 0
p = 0
for i in range(m+1):
    while p < n and ab[p][0] <= i:
        heapq.heappush(pq, -ab[p][1])
        p += 1

    if len(pq) == 0:
        continue

    ans -= heapq.heappop(pq)

print(ans)
import math

data = list(map(int, input().split()))
A, B = data[0], data[1]
g = math.gcd(A, B)
lcd = int(A*B/g)
print(lcd)

### FIXED CODE ###

data = list(map(int, input().split()))
A, B = data[0], data[1]

def gcd(A, B):
    x = max(A, B)
    y = min(A, B)
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            z = x % y
            x = y
            y = z
        else:
            return z

def lcd(A, B):
    return A * B // gcd(A, B)

print(lcd(A, B))
from itertools import*;from scipy.sparse.csgraph import*
N,M,R=map(int,input().split());r=map(int,input().split())
G=[[9e9]*N for _ in[0]*N]
for _ in[0]*M:A,B,C=map(int,input().split());G[A-1][B-1]=G[B-1][A-1]=C
D=dijkstra(G)
print(int(min(sum(D[i-1,j-1]for i,j in zip(t,t[1:]))for t in permutations(r))))

### FIXED CODE ###

from itertools import*;from scipy.sparse import*
N,M,R=map(int,input().split());r=map(int,input().split())
G=[[9e9]*N for _ in[0]*N]
for _ in[0]*M:A,B,C=map(int,input().split());G[A-1][B-1]=G[B-1][A-1]=C
D=csgraph.dijkstra(csr_matrix(G))
print(int(min(sum(D[i-1,j-1]for i,j in zip(t,t[1:]))for t in permutations(r))))
a,b,c=map(int,input().split())
v=sorted([int(input())for i in range(a)])
print(v)
bus=[]
ans=0
for i in range(a-1):
    
    if v[i]+c<v[i+1]:
        ans+=1
        bus=[]
        if i==a-2:
            ans+=1
    else:
        bus.append(v[i])
        print(bus)
        if len(bus)>=b:
            ans+=1
            bus=[]
if len(bus)>0:
    ans+=1
print(ans)

### FIXED CODE ###

n,c,k,*t=map(int,open(0).read().split())
t.sort()
totalbus=1
bus=0
time=t[0]
for i in range(n):
    bus+=1
    if t[i]>time+k or bus>c:
        time=t[i]
        totalbus+=1
        bus=1
print(totalbus)