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

n,k = map(int,input().split())
h = []
ans = 1<<50
for i in range(n):
    h.append(int(input()))
h = sorted(h)
for i in range(n-k+1):
    temp = h[i:i+k]
    # print(temp)
    ans = min(ans,temp[-1]-temp[0])
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
h = []
ans = 1<<50
for i in range(n):
    h.append(int(input()))
h = sorted(h)
for i in range(n-k+1):
    ans = min(ans,h[i+k-1]-h[i])
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
f = [10**9 for x in range(X + 1)]
f[0] = 0
for n in range(N):
    f = [
        min(f[x], f[x - V[n]] + W[n]) if x >= V[n] else f[x]
        for x in range(X + 1)
    ]
for x in range(X + 1)[::-1]:
    if f[x] <= M:
        print(x)
        exit()


### FIXED CODE ###

N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
X = sum(V)
# f[n][x] = n番目までの品物でx以上の価値に必要な最小の重さ
f = [[10**9 for x in range(X + 1)] for n in range(N + 1)]
f[0][0] = 0
for n in range(1, N + 1):
    for x in range(X + 1):
        if x >= V[n - 1]:
            f[n][x] = min(f[n - 1][x], f[n - 1][x - V[n - 1]] + W[n - 1])
        else:
            f[n][x] = f[n - 1][x]
ans = X
while f[N][ans] > M:
    ans = ans - 1
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

a,b,c = map(int,input().split())
count = 0
for i in range(a,b+1):
  if i % c == 0:
    count += 1
print(count)

### FIXED CODE ###

import sys
input=sys.stdin.readline

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

if a%c ==0:
	ans = b//c - a//c+1
else:
	ans = b//c - a//c
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
import math

l_s = []
c = 0
n = int(input())
for i in range(n):
    s = input()
    c += l_s.count(sorted(s))
    l_s.append(sorted(s))

print(c)

### FIXED CODE ###

#!/usr/bin/env python
import math

l_s = set()
c = 0
n = int(input())
dup = {}

for i in range(n):
    st = sorted(input())
    s  = "".join(st)
    if s in l_s:
        if s in dup.keys():
            dup[s] += 1
        else:
            dup[s] = 1
        c += dup[s]
    l_s.add(s)

print(c)
### BUGGY CODE ###

n=int(input())
#i+j-2=cnt & i*j=n
import math
minn=10000000000000000
for i in range(1,math.floor(n)):
    if n%i==0:
        j=n/i
        minn=min(int(i+j-2),int(minn))
    else:
        continue
print(minn)

### FIXED CODE ###

n=int(input())
#i+j-2=cnt & i*j=n
import math
minn=100000000000000000000
for i in range(1,int(math.sqrt(n))+2):
    if n%i==0:
        j=n/i
        minn=min(int(i+j-2),minn)
print(minn)
### BUGGY CODE ###

n = int(input())
xl, yl = [], []
for _ in range(n):
    x, y = map(int, input().split())
    xl.append(x)
    yl.append(y)
xl_ = xl.copy()
yl_ = yl.copy()
xl_.sort()
yl_.sort()
xm = xl_[n//2-1]
ans = 0
for k in range(min(n, 1000)):
    ym = yl[k]
    ans1, ans2, ans3, ans4 = 0, 0, 0, 0
    for i in range(n):
        if xl[i] > xm:
            if yl[i] > ym:
                ans1 = max(ans1, abs(xl[i]-xm)+abs(yl[i]-ym))
            else:
                ans4 = max(ans4, abs(xl[i]-xm)+abs(yl[i]-ym))
        else:
            if yl[i] > ym:
                ans2 = max(ans2, abs(xl[i]-xm)+abs(yl[i]-ym))
            else:
                ans3 = max(ans3, abs(xl[i]-xm)+abs(yl[i]-ym))
ans = int(max(abs(ans1+ans3), abs(ans2+ans4)))

print(ans)





### FIXED CODE ###

n = int(input())
xy = [list(map(int, input().split())) for _ in range(n)]
f0 = sorted([x+y for x, y in xy])
f1 = sorted([x-y for x, y in xy])
print(max(f0[-1]-f0[0], f1[-1]-f1[0]))
### BUGGY CODE ###

def main():
    n = int(input())
    keys = []
    for i in xrange(n):
        keys.append(map(int,raw_input().split())+[i])

    T = Tree()
    T.recursive_add_Node(keys,0)

    q = int(input())
    for i in xrange(q):
        sx, tx, sy, ty = map(int,raw_input().split())
        nums = []
        find(T.root,[sx,sy],[tx,ty],0,nums)
        nums.sort()
        for i in nums:
            print i
        print ""
        

def find(z,s,t,d,nums):
    if(s[0]<=z.key[0]<=t[0])and(s[1]<=z.key[1]<=t[1]):
        nums.append(z.num)

    d += 1
    if (z.left != None)and(z.key[d%2]>=s[d%2]):
        find(z.left,s,t,d,nums)
    if (z.right != None)and(z.key[d%2]<=t[d%2]):
        find(z.right,s,t,d,nums)


class Tree():
    def __init__(self):
        self.root = None

    def add_Node(self,k,n):
        y = None
        x = self.root
        d = 0
        while(x != None):
            d += 1
            y = x
            if x.key[d%2] > k[d%2]:
                x = x.left
            else:
                x = x.right
        
        z = Node(k,n)
        z.parent = y
        z.depth  = d

        if y == None:
            self.root = z
        elif y.key[d%2] > k[d%2]:
            y.left = z
        else:
            y.right = z
        
    def recursive_add_Node(self,keys,depth):
        keys.sort(key=lambda x:x[depth%2])
        id_mean = len(keys)/2
        self.add_Node(keys[id_mean][:2],keys[id_mean][2])

        keys_l = keys[:id_mean]
        keys_r = keys[id_mean+1:]
       
        if keys_l:
            self.recursive_add_Node(keys_l,depth+1)
        if keys_r:
            self.recursive_add_Node(keys_r,depth+1)

class Node():
    def __init__(self,k,n):
        self.key    = k
        self.num    = n
        self.depth  = None
        self.parent = None
        self.left   = None
        self.right  = None
    


if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin,stdout
import math
from operator import itemgetter
from bisect import bisect_left, bisect_right
readline = stdin.readline
 
def main():
    n = int(input())
    keys = map(lambda i: map(int,readline().split())+[i], xrange(n))
    keys.sort()

    root = int(math.sqrt(len(keys)))
 
    low = [x for x, y, i in keys[::root]]
    high = [x for x, y, i in keys[root - 1::root]] + [float('inf')]
 
    keys = [sorted(keys[i:i+root], key=itemgetter(1)) for i in range(0,len(keys),root)]
    keys_y = map(lambda k:[y for x,y,i in k], keys)

    q = int(input())
    for i in xrange(q):
        sx,tx,sy,ty = map(int,readline().split())
        
        nums = []
        for i in range(bisect_left(high, sx), bisect_right(low, tx)):
            y = keys_y[i]
            for j in range(bisect_left(y, sy), bisect_right(y, ty)):
                if sx <= keys[i][j][0] <= tx:
                    nums.append(keys[i][j][2])
        if nums:
            nums.sort()
            map(lambda n:stdout.write("{}\n".format(n)), nums)
        print("")

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

#%%
import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
l = callIsPrime(10**6)

x = int(input())
for i in range(len(l)):
    if l[i] >= x:
        print(l[i])
        break

# %%


### FIXED CODE ###


#%%
import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=(10**5) * 2):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
l = callIsPrime((10**5) * 2)
#print(l)

x = int(input())
for i in range(len(l)):
    if l[i] >= x:
        print(l[i])
        break

# %%
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
import itertools
ans = 0
for v in itertools.combinations(a, 2):
    ans += v[0]*v[1]
print(ans%(10 ** 9 + 7))

### FIXED CODE ###

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

ans = 0

sum_a = sum(a)


for i in range(n):
    ans += a[i] * (sum_a - a[i])
    sum_a -= a[i]

print(ans%(10 ** 9 + 7))
### BUGGY CODE ###

import sys
import collections
import math
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n = I()
mylist = sorted(list(MI()))
max_num = int(math.sqrt(mylist[n-1]))
start = mylist[0]
input_list = [0] * n
index = 0

while len(mylist) >= 1:
    temp = mylist.pop(0)
    if not(temp in mylist):
        index += 1
    for j in set(mylist):
        if j % temp == 0:
            while j in mylist:
                mylist.remove(j)
print(index)

### FIXED CODE ###

import sys
import collections
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    n = I()
    mylist = list(MI())
    max_a = max(mylist)
    exclude_set = set()
    tlist = [False] * (max_a+1)
    for a in mylist:
        if tlist[a]:
            exclude_set.add(a)
        else:
            tlist[a] = True
    ans = 0
    
    for i in range(1, max_a//2 + 1):
        if not tlist[i]:
            continue
        else:
            for j in range(2*i, max_a+1, i):
                tlist[j]=False
    for i in range(len(tlist)):
        if tlist[i] and not i in exclude_set:
            ans += 1
    print(ans)
                
    

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

n = int(input())

label = []
num = {}

for i in range(n):
    seq = input()
    seq = ''.join(sorted(seq))
    if seq in label:
        num[seq] += 1
    else:
        label.append(seq)
        num[seq] = 1

ans = 0
for s in num:
    k = num[s]
    if k > 1:
        ans += k * (k-1) // 2

print(ans)

### FIXED CODE ###

n = int(input())

num = {}

for i in range(n):
    seq = input()
    seq = ''.join(sorted(seq))
    if seq in num:
        num[seq] += 1
    else:
        num[seq] = 1

ans = 0
for s in num:
    k = num[s]
    if k > 1:
        ans += k * (k-1) // 2

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

def main():
    N = int(input())
    P = [None] + list(map(int, input().split()))

    p_to_index = [None] * (N + 1)
    for index, x in enumerate(P[1:], 1):
        p_to_index[x] = index

    #大きい数から挿入
    #左隣にあるインデックスを取得できるようにする
    #[1, i]内で書き込んだ数の個数を獲得できるBITを構築する

    def BIT_add(i):
        while i <= N:
            tree[i] += 1
            i += i & (-i)

    def BIT_sum(i):
        s = 0
        while i:
            s += tree[i]
            i -= i & (-i)
        return s

    def BIT_search(x):
        i = 0
        s = 0
        step = 1 << (N.bit_length() - 1)
        while step:
            if i + step <= N and s + tree[i + step] < x:
                i += step
                s += tree[i]
            step >>= 1
        return i + 1

    tree = [0] * (N + 1)
    ans = 0
    for x in range(N, 0, -1):
        c = p_to_index[x]
        L = BIT_sum(c) #左側にある既に書き込んだ数の個数
        BIT_add(c)
        R = N - x - L #右側にある既に書き込んだ数の個数
        a = BIT_search(L - 1) if L >= 2 else 0
        b = BIT_search(L) if L >= 1 else 0
        d = BIT_search(L + 2) if R >= 1 else N + 1
        e = BIT_search(L + 3) if R >= 2 else N + 1
        if b != 0:
            ans += x * (b - a) * (d - c)
        if d != 0:
            ans += x * (e - d) * (c - b)

    print (ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

index_lst = [0] * N
for index, i in enumerate(P):
    index_lst[i - 1] = index

left_next_Index = list(range(-1, N - 1)) + [-1, -1]
right_next_Index = list(range(1, N + 1)) + [N, N]
# print (left_next_Index)
# print (right_next_Index)
ans = 0
for i in range(1, N):
    index = index_lst[i - 1]
    # print (i, index)
    l1 = left_next_Index[index]
    l2 = left_next_Index[l1]
    r1 = right_next_Index[index]
    r2 = right_next_Index[r1]
    # print ('l1 =', l1, ' l2 =', l2, ' r1 =', r1, ' r2 =', r2)
    ans += i * ((index - l1) * (r2 - r1) + (r1 - index) * (l1 -l2))

    left_next_Index[r1] = l1
    right_next_Index[l1] = r1

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

n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 400000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)

### FIXED CODE ###

n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 30000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)
### BUGGY CODE ###

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

for _ in range(q):
    tmp = input()
    if len(tmp) == 1:
        s = s[::-1]
    else:
        if tmp[2] == str(2):
            s = s + tmp[-1]
        else:
            s = tmp[-1] + s

print(s)

### FIXED CODE ###

s = input()
q = int(input())
before = []
after = []
isReversed = 0


for _ in range(q):
    tmp = input()
    if len(tmp) == 1:
        if isReversed:
            isReversed = 0
        else:
            isReversed = 1
    else:
        if tmp[2] == str(2):
            if isReversed:
                before.append(tmp[-1])
            else:
                after.append(tmp[-1])
        else:
            if isReversed:
                after.append(tmp[-1])
            else:
                before.append(tmp[-1])


if isReversed:
    ans = "".join(after[::-1]) + s[::-1] + "".join(before)
    print(ans)

else:
    ans = "".join(before[::-1]) + s + "".join(after)
    print(ans)
### BUGGY CODE ###

import sys
import fractions
sys.setrecursionlimit(100000)
def lcm(x,y):
    return x/fractions.gcd(x,y)*y

n = int(input())
a = list(map(int,input().split()))
LCM=a[0]
for i in a:
  LCM = lcm(LCM,i)
ans=0
for i in a:
  ans += LCM/i
  ans %= 1000000007
  
print(int(ans))


### FIXED CODE ###

import sys
import fractions
sys.setrecursionlimit(100000)
def lcm(x,y):
    return x//fractions.gcd(x,y)*y

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

s=list(input())
n=len(s)

cnt=0
i=0
while i<n-2:
    if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
        s[i]="B"
        s[i+1]="C"
        s[i+2]="A"
        cnt+=1
        if i!=0:
            i-=1
    else:
        i+=1

print(cnt)

### FIXED CODE ###

s=input()
n=len(s)

cnt=0
ans=0

for i in range(n-1):
    if s[i]=="A":
        cnt+=1
    elif s[i:i+2]=="BC":
        ans+=cnt
    elif i>0 and s[i-1:i+1]=="BC":
        pass
    else:
        cnt=0

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

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

for i in range(m):
    maxa = max(a)
    if maxa == 0:
        break
    a[a.index(maxa)] = maxa // 2
print(sum(a))

### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline
 
n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] *= -1
heapq.heapify(a)
 
for cnt in range(m):
    temp = heapq.heappop(a)*(-1)
    if temp == 0:
        break
    heapq.heappush(a, (temp//2)*(-1))
    
print(sum(a)*(-1))
### BUGGY CODE ###

import random

def is_prime(q,k=50):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))
if m%n>100000:
  for i in range(1,n):
    if m%i==0 and is_prime(i) and is_prime(m//i) and (i==1 or m//i<n):
      print('1')
      exit()
for i in range(n,m+1):
  if i==m:
    print(1)
    break
  if m%i==0:
    print(m//i)
    break
  if m-i-n>0 and m%(m-i-n)==0 and m//(m-i-n)>n:
    print(m-i-n)
    break


### FIXED CODE ###

import random

def is_prime(q,k=50):
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

n,m=(int(i) for i in input().split(' '))
for i in range(1,n):
  if m%i==0 and (is_prime(i) or i==1) and is_prime(m//i) and (i==1 or m//i<n):
    print('1')
    exit()
for i in range(n,m+1):
  if i==m:
    print(1)
    break
  if m%i==0:
    print(m//i)
    break
  if m-i-n>0 and m%(m-i-n)==0 and m//(m-i-n)>n:
    print(m-i-n)
    break
### BUGGY CODE ###

N = int(input())
S = input()
R = []
G = []
B = []
for i, s in enumerate(S):
    if s == 'R':
        R.append(i+1)
    elif s == 'G':
        G.append(i+1)
    else:
        B.append(i+1)
res = []
# RGB
for a in R:
    for b in [b for b in G if b > a]:
        for c in [c for c in B if c > b]:
            res.append([a, b, c])
# RBG
for a in R:
    for b in [b for b in B if b > a]:
        for c in [c for c in G if c > b]:
            res.append([a, b, c])
# BRG
for a in B:
    for b in [b for b in R if b > a]:
        for c in [c for c in G if c > b]:
            res.append([a, b, c])
# BGR
for a in B:
    for b in [b for b in G if b > a]:
        for c in [c for c in R if c > b]:
            res.append([a, b, c])
# GRB
for a in G:
    for b in [b for b in R if b > a]:
        for c in [c for c in B if c > b]:
            res.append([a, b, c])
# GBR
for a in G:
    for b in [b for b in B if b > a]:
        for c in [c for c in R if c > b]:
            res.append([a, b, c])
print(len([x for x in res if x[1] - x[0] != x[2] - x[1]]))

### FIXED CODE ###

from collections import Counter

N = int(input())
S = input()
RGB_Counter = Counter(S)
ans = RGB_Counter['R'] * RGB_Counter['G'] * RGB_Counter['B']

dum = []
d = 0
while 3 + d*2 <= N:
    for i in range(N - 2*(d+1)):
        a = S[i]
        b = S[i+d+1]
        c = S[i+2*(d+1)]
        if a != b and b != c and c != a:
            ans -= 1
    d += 1

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

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

def solve(k,n,a):
    for _ in range(k):
        Y = [0]*(n+1)
        for i, x in enumerate(a):
            Y[max(0, i-x)] += 1
            Y[min(n, i+x+1)] -= 1
        for j in range(1, n):
            Y[j] += Y[j-1]
        if a == Y[:-1]:
            break
        a = Y[:-1]
    return a

ans=solve(K,N,A)
print(*ans)

### FIXED CODE ###

from numba import jit
N, K = map(int, input().split())
A = list(map(int, input().split()))

@jit
def solve(k,n,a):
    for _ in range(k):
        Y = [0]*(n+1)
        for i, x in enumerate(a):
            Y[max(0, i-x)] += 1
            Y[min(n, i+x+1)] -= 1
        for j in range(1, n):
            Y[j] += Y[j-1]
        if a == Y[:-1]:
            break
        a = Y[:-1]
    return a

ans=solve(K,N,A)
print(*ans)
### BUGGY CODE ###

n,m = map(int, input().split())

ans = 0
for i in range(n, 0, -1):
  if m >= 2*i:
    ans += i
    m -= 2*i
    break

if m >= 4:
  ans += m // 4
  
print(ans)

### FIXED CODE ###

n,m = map(int, input().split())

ans = 0
if n*2 <= m:
  ans += n
  m -= n*2
else:
  ans += m//2
  m %= 2

if m >= 4:
  ans += m // 4
  
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
P = []
Y = []
arr = [[]for j in range(10**5+1)]
for i in range(M):
  listA = list(map(int,input().split()))
  P.append(listA[0])
  Y.append(listA[1])
  arr[listA[0]].append(listA[1])
  arr[listA[0]].sort()
for i in range(M):
  left = 0
  right = len(arr[P[i]])-1
  while left <= right:
    mid = (left+right)//2
    if arr[P[i]][mid] == Y[i]:
      k = mid
      break
    elif arr[P[i]][mid] > Y[i]:
      right = mid-1
    else:
      left = mid+1
  print(str(P[i]).rjust(6,'0')+str(k+1).rjust(6,'0'))

### FIXED CODE ###

N,M = map(int,input().split())
P = []
Y = []
arr = [[]for j in range(10**5+1)]
for i in range(M):
  listA = list(map(int,input().split()))
  P.append(listA[0])
  Y.append(listA[1])
  arr[listA[0]].append(listA[1])
for i in range(N+1):
  arr[i].sort()
for i in range(M):
  #二部探索
  left = 0
  right = len(arr[P[i]])-1
  while left <= right:
    mid = (left+right)//2
    if arr[P[i]][mid] == Y[i]:
      k = mid
      break
    elif arr[P[i]][mid] > Y[i]:
      right = mid-1
    else:
      left = mid+1
  print(str(P[i]).rjust(6,'0')+str(k+1).rjust(6,'0'))
### BUGGY CODE ###

N, M = map(int,input().split())
A = [int(i) for i in input().split()]
sumA = [int(sum(A[:i]) % M) for i in range(N + 1)]
ans = 0

for j in range(N):
    ans += sumA[j:].count(sumA[j]) - 1

print(ans)

### FIXED CODE ###

from collections import defaultdict as dict
d = dict(int)
N, M = map(int,input().split())
A = [int(i) for i in input().split()]
sumA = [0 for i in range(N + 1)]
for i in range(N):
    sumA[i + 1] = (A[i] + sumA[i]) % M
ans = 0

for j in range(len(sumA)):
    ans += d[sumA[j]]
    d[sumA[j]] += 1

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

N = int(input())
A,B,C,D,E = [int(input()) for _ in range(5)]
S = [0] * 5
S[0] = N
count = 0
while True :
    if S[4] > 0 :
        if S[4] - E >= 0 :
            S[4] =  S[4] - E
        else :
            S[4] = 0
    if S[3] > 0 :
        if S[3] - D >= 0:
            S[3] = S[3] - D
            S[4] = S[4] + D
        else :
            S[4] = S[4] + S[3]
            S[3] = 0
    if S[2] > 0:
        if S[2] - C >= 0:
            S[2] = S[2] - C
            S[3] = S[3] + C
        else:
            S[3] = S[3] + S[2]
            S[2] = 0
    if S[1] > 0:
        if S[1] - B >= 0:
            S[1] = S[1] - B
            S[2] = S[2] + B
        else:
            S[2] = S[2] + S[1]
            S[1] = 0
    if S[0] > 0:
        if S[0] - A >= 0:
            S[0] = S[0] - A
            S[1] = S[1] + A
        else:
            S[1] = S[1] + S[0]
            S[0] = 0

    #print(S)
    count += 1
    if S[0] == 0 and S[1] == 0 and S[2] == 0 and S[3] == 0 and S[4] == 0 :
        break

print(count)


### FIXED CODE ###

import math
N = int(input())
A = [int(input()) for i in range(5)]
print(math.ceil(N/min(A))+4)
### BUGGY CODE ###

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
for i in range(n):
  if sum(a[:i+1])>k:
    break
  elif sum(a[:i+1])+sum(b)<=k:
      ans=max(ans,i+m+1)
  else:  
    for j in range(m):
      if sum(a[:i+1])+sum(b[:j+1])<=k:
        continue
      else:
        ans=max(ans,i+j+1)
        break
print(ans)

### FIXED CODE ###

import itertools
import bisect
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=[0]+list(map(int,input().split()))
a=list(itertools.accumulate(a))
b=list(itertools.accumulate(b))
ans=0
for i in range(m+1):
  x=k-b[i]
  y=bisect.bisect_right(a,x)
  z=i+y
  if x<0:
      z=0
  ans=max(ans,z)
print(ans)