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

import sys

sys.setrecursionlimit(10 ** 7)

n, m = input().split(' ')
N = int(n)
M = int(m)

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

# 報酬がi日後までにもらえるタスクの中(pool)で報酬が最大ものを選んでいく。
# 最大 M-1 回働ける
index = 0
pool = []
rewords = 0
for i in range(M):
    day = i + 1

    while index < N and day >= int(sorted_ab[index][0]):
        pool.append(int(sorted_ab[index][1]))
        index += 1
    # pool の中にある仕事の中から最大の報酬のものを選ぶ
    if pool:
        max_reword = max(pool)
        rewords += max_reword
        pool.remove(max_reword)

print(rewords)


### FIXED CODE ###

import sys
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)

n, m = input().split(' ')
N = int(n)
M = int(m)

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

# 報酬がi日後までにもらえるタスクの中(pool)で報酬が最大ものを選んでいく。
# 最大 M-1 回働ける
index = 0
pool = []
rewords = 0
for i in range(M):
    day = i + 1

    while index < N and day >= int(sorted_ab[index][0]):
        heappush(pool, -sorted_ab[index][1])
        index += 1
    # pool の中にある仕事の中から最大の報酬のものを選ぶ
    if pool:
        rewords += -heappop(pool)

print(rewords)
### BUGGY CODE ###

s = input()
n = len(s)
ans = 0
a = []
for i in range(n-3):
    for j in range(i+3, n+1):
        if int(s[i:j])%2019==0:
            ans+=1
            a.append((i, j))
print(ans)

### FIXED CODE ###

s = input()

n = len(s)
c = [0]*2019
c[0]+=1
t = 0
digit = 1
for ss in s[::-1]:
    t = (t+int(ss)*digit) % 2019
    digit = (digit * 10) % 2019
    c[t]+=1
ans = 0
ans = sum(cc*(cc-1)//2 for cc in c)
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
ans=0
ns=str(n)
l=[]
ls=len(ns)
for i in range(ls):
    l.append(int(ns[ls-1-i]))
for i in range(10**6+1-ls):
    l.append(0)
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)








### FIXED CODE ###

import sys
input=sys.stdin.readline
ns=input().rstrip()
ans=0
l=[]
ls=len(ns)
for i in range(ls):
    l.append(int(ns[ls-1-i]))
for i in range(10**6+1-ls):
    l.append(0)
for i in range(10**6+1):
    if 0<=l[i]<=4:
        ans+=l[i]
    elif 6<=l[i]<=9:
        ans+=10-l[i]
        l[i+1]+=1
    elif l[i]==10:
        l[i+1]+=1
    elif l[i]==5:
        ans+=5
        if 0<=l[i+1]<=4:
            pass
        else:
            l[i+1]+=1
print(ans)
### BUGGY CODE ###

s = input()

count = []

for i in range(len(s)):
    if s[i] == "A":
        for j in range(i+1,len(s)):
            if s[j] == "Z":
                count.append(j-i+1)
print(max(count))

### FIXED CODE ###

s = input()

pos_a = s.find("A")
pos_z = s.rfind("Z")

print(pos_z -pos_a +1)
### BUGGY CODE ###

n,m = map(int,input().split(" "))
ar = [[] for i in range(n)]
br = [0 for i in range(n-1)]
for i in range(m):
    x,y = map(int,input().split(" "))
    ar[x-1].append(y-1)
    ar[y-1].append(x-1)
del ar[0]
cr = [0]
dr = []
for r in cr:
    for i in range(n-1):
        if r in ar[i] and br[i] == 0:
            br[i] = r + 1
            cr.append(i+1)
print("Yes")
for r in br:
    print(r)

### FIXED CODE ###

n,m = map(int,input().split(" "))
ar = [[] for i in range(n)]
br = [0 for i in range(n)]
for i in range(m):
    x,y = map(int,input().split(" "))
    ar[x-1].append(y-1)
    ar[y-1].append(x-1)
cr = [0]
dr = []
for r in cr:
    for i in ar[r]:
        if br[i] == 0:
            br[i] = r + 1
            cr.append(i)
print("Yes")
for i in range(1,n):
    print(br[i])
### BUGGY CODE ###

for e in iter(input,'-1'):
 q=float(e)
 x=q/2
 while abs(x**3-q)-q*1e-5:x-=(x**3-q)/(3*x*x)
 print(x)


### FIXED CODE ###

for e in iter(input,'-1'):
 q=float(e)
 x=q/2
 while abs(x**3-q)>=q*1e-5:x-=(x**3-q)/3/x/x
 print(x)
### BUGGY CODE ###

import numpy as np

N,M=map(int,input().split())
# N,M=3,3
A = list(map(int,input().split()))
#dymmy
# A.append(-1)
# A=[2,13,8]
# print(np.argmax(A))

# print(N,M,A)
# Val = sorted(A,reverse=True)
# print("割引前",Val)

#Ｍ枚の商品券を持っているため
for i in range(M):
    A[np.argmax(A)]= A[np.argmax(A)]//2
    # if Val[0] < Val[1]:
        # Val = sorted(Val,reverse=True)

# print("計算後",Val)
print(sum(A))

### FIXED CODE ###

import numpy as np

N,M=map(int,input().split())
# N,M=4,4
A = list(map(int,input().split()))
#dymmy
A.append(-1)
# A=[1,9,3,5]
# print(np.argmax(A))

# print(N,M,A)
Val = sorted(A,reverse=True)
# print("割引前",Val)

#Ｍ枚の商品券を持っているため
hoge =Val[0]

if N==1:
    print(Val[0]//(2**M))
    exit(0)
if M==1:
    Val[0]//=2
    print(sum(Val)+1)
    exit(0)
# for i in range(M):
#     # A[np.argmax(A)]= A[np.argmax(A)]//2
#     Val[0]//=2
#     for i in range(1,M):
#         if Val[0]<Val[i]:
#             Val[0],Val[i] = Val[i],Val[0]
#             break
#         else:
#             pass
i=0
while i<M:
    # A[np.argmax(A)]= A[np.argmax(A)]//2
    i+=1
    Val[0]//=2
    if i>=M:
        break
    for j in range(1,M):
        if i<M and Val[0]<Val[j]:
            Val[j]//=2
            i+=1
        else:
            Val = sorted(Val,reverse=True)
            break
    

# print(Val)
print(sum(Val)+1)
### BUGGY CODE ###

N = int(input())

N_str = str(N)
n = len(N_str)
num = 0
for i in range(3,n):
    num += (3**i-3*2**i+3)

def number(x):
    List = []
    X = str(x)
    for i in range(len(X)):
        List.append(int(X[i]))
    a = List.count(3)
    b = List.count(5)
    c = List.count(7)
    if a>=1 and b>=1 and c>=1 and a+b+c==len(X):
        return True
    else:
        return False

c = 10**(n-1)+1
if N > 10**7:
    if int(N_str[0]) > 7:
        num += (3**n-3*2**n+3)
        c = N+1
    elif int(N_str[0]) > 5:
        num += (3**n-3*2**n+3)*2//3
        c =6*10**(n-1)+1
    elif int(N_str[0]) > 3:
        num += (3**n-3*2**n+3)//3
        c =4*10**(n-1)+1


while c <= N:
    if number(c):
        num += 1
    c += 2

print(num)

### FIXED CODE ###

N = int(input())


List = []
n = len(str(N))
ans = 0
if n >= 3:
    if n > 3:
        for i in range(2,n-1):
            ans += (3**(i+1)-3*2**(i+1)+3)
    for j in range(n):
        if j == 0:
            List = [3*10**(n-1),5*10**(n-1),7*10**(n-1)]
        else:
            for k in range(3**j):
                num = List.pop(0)
                List.append(num+3*10**(n-j-1))
                List.append(num+5*10**(n-j-1))
                List.append(num+7*10**(n-j-1))
    for l in range(len(List)):
        if List[l] <= N:
            s = str(List[l])
            if "3" in s and "5" in s and "7" in s:
                ans += 1

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

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

DP = [0 for _ in range(N)]

for i in range(1,N):
	temp = []
	for j in range(min(i,K)):
		temp.append(DP[i-(j+1)] + abs(H[i]-H[i-(j+1)]))

	DP[i] = min(temp)

print(DP[N-1])

### FIXED CODE ###

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

DP = [0 for _ in range(N)]

for i in range(1,N):
	temp = []
	for j in range(min(i,K)):
		temp.append(DP[i-(j+1)] + abs(H[i]-H[i-(j+1)]))

	DP[i] = min(temp)

print(DP[N-1])
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    l = 29
    val = 0
    from bisect import bisect_left as bll, bisect_right as brr
    def bl(bb, ind):
        if ind in dl:
            return dl[ind]
        else:
            tt = bll(bb, ind)
            dl[ind] = tt
            return tt
    def br(bb, ind):
        if ind in dr:
            return dr[ind]
        else:
            tt = brr(bb, ind)
            dr[ind] = tt
            return tt  

    for k in range(l):
        # i桁目を求める
        tmp = pow(2, k+1)
        bb = [item%(tmp) for item in b]
        bb.sort()
        ans = 0
        dl = {}
        dr = {}
        for item in a:
            aa = item%tmp
            if aa<=tmp//2:
                ans += (br(bb, tmp-1-aa) - bl(bb, tmp//2-aa))%2
            else:
                ans += (br(bb, tmp-1-aa) + (n - bl(bb, tmp//2*3-aa)))%2
        if ans%2:
            val += pow(2, k)
    print(val)
main()

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = 29
val = 0

def lcount(a,b,x):
    """ソート済a,bに対して, a[i]+b[j]<=xなるi,jの個数
    """
    la = len(a)
    lb = len(b)
    j = -1
    ans = 0
    for i in range(la-1, -1, -1):
        while j+1<lb and a[i]+b[j+1]<=x:
            j += 1
        ans += (j+1)
    return ans
for k in range(l):
    # i桁目を求める
    tmp = pow(2, k+1)
    bb = [item%(tmp) for item in b]
    aa = [item%(tmp) for item in a]
    aa.sort()
    bb.sort()
    ans = n**2 - lcount(aa,bb,tmp//2*3-1) + lcount(aa,bb,tmp-1) - lcount(aa,bb,tmp//2-1)
    if ans%2:
        val += pow(2, k)
print(val)
### BUGGY CODE ###

x, k, d = [int(i) for i in input().split()]
x = abs(x)
if k * d <= x:
    print(x - k*d)
else:
    while x - d > 0:
        x -= d
        k -= 1
    if k & 1:
        print(d - x)
    else:
        print(x)

### FIXED CODE ###

x, k, d = [int(i) for i in input().split()]
x = abs(x)
if k * d <= x:
    print(x - k*d)
else:
    t = x
    x %= d
    k = k - (t - x)//d
    if k & 1:
        print(abs(d - x))
    else:
        print(x)
### BUGGY CODE ###

n=int(input())
h=list(map(int,input().split()))
ans=0
while any(h)==True:
    flag=0
    for i in range(n-1):
        if h[i]>0:
            h[i]-=1
            flag=1
        else:
            if flag==1:
                ans+=1
                flag=0
        if i==n-2:
            if h[n-1]>0:
                h[n-1]-=1
                ans+=1
                break
            else:
                if h[i]>-1 and flag==1:
                    ans+=1
                break
print(ans)


### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
ans=0
if n==1:
    print(h[0])
    exit()
while any(h)==True:
    flag=0
    for i in range(n-1):
        if h[i]>0:
            h[i]-=1
            flag=1
        else:
            if flag==1:
                ans+=1
                flag=0
        if i==n-2:
            if h[n-1]>0:
                h[n-1]-=1
                ans+=1
            else:
                if flag==1:
                    ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())

d = {}
for i in range(n):
  s = input()
  if s in d.keys():
    d[s] += 1
  else:
    d[s] = 1

m = max(d.values())
ans = []

for k, v in d.items():
  if v == m:
    ans.append(k)
ans.sort()
print(*ans, sep = "\n")

### FIXED CODE ###

from collections import Counter

n = int(input())
s = [input() for _ in range(n)]

c = Counter(s)
c = c.most_common()
ans_number = c[0][1]
c.sort()

for i in range(len(c)):
  if c[i][1] == ans_number:
    print(c[i][0])
### BUGGY CODE ###

import math
def is_prime(x):
    if x <= 1:
        return False
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True

n = int(input())
lst_c = []
for c in range(1,n): #c != n
    lst_c.append(n-c)

for i in range(len(lst_c)):
    if is_prime(lst_c[i]):
        lst_c[i] = 1

#print(lst_c)

cnt = 0
cnt2 = 0
for i in range(len(lst_c)):
    if lst_c[i] != 1:
        for j in range(1,int(lst_c[i]**0.5)+1):
            if lst_c[i]%j ==0:
                cnt += 1
                if lst_c[i]/j == j:
                    cnt2 +=1
        lst_c[i] = cnt
        cnt = 0
        #cnt2 = 0


print(sum(lst_c)*2-cnt2-1)
#print(lst_c)

### FIXED CODE ###

def func(x):
    ans = 0
    for a in range(1, n):
        for b in range(1, n):
            c = n - a * b
            if c <= 0:
                break
            ans += 1
    return ans

n = int(input())
print(func(n))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
sum=0
for k in range(0,len(a)):
  if a.count(a[k])>1:
    sum=sum+1
if sum==0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
if len(a)==len(list(set(a))):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(n//b+1):
    for j in range(n//g+1):
        for k in range(n//r+1):
            if r*k+g*j+b*i==n:
                ans=ans+1
            elif r*k+g*j+b*i>n:
                break
        if g*j+b*i>n:
            break
print(ans)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(n//b+1):
    bi=b*i
    for j in range(n//g+1):
        gj=g*j
        if gj+bi>n:
            break
        elif gj+bi==n:
            ans=ans+1
            break
        elif (n-(gj+bi))%r==0:
            ans=ans+1
print(ans)
### BUGGY CODE ###

s = str(input())
K = int(input())

s2 = ''.join(sorted(set(list(s))))

l = []

for i in range(len(s2)):
  if len(set(l)) >= K:
    #print(i)
    break
  else:
    for j in range(len(s)):
      if s2[i] == s[j]:
        for k in range(j+1, len(s)+1):
          l.append(s[j:k])
l = list(set(l))
l.sort()
#print(l)
print(l[K-1])

### FIXED CODE ###

s = str(input())
K = int(input())

s2 = ''.join(sorted(set(list(s))))

l = []

for i in range(len(s2)):
  if len(set(l)) >= K:
    #print(i)
    break
  else:
    for j in range(len(s)):
      if s2[i] == s[j]:
        for k in range(j+1, len(s)+1):
          if k-j > K:
            break
          else:
            l.append(s[j:k])
l = list(set(l))
l.sort()
#print(l)
print(l[K-1])
### BUGGY CODE ###

import math

def read():
    X = int(input().strip())
    return X,


def solve(X):
    A = [100 ,101, 102, 103, 104, 105]
    NA = 6
    dp = [[False for j in range(X+1)] for i in range(NA+1)]
    for i in range(NA+1):
        dp[i][0] = True
    for i in range(NA):
        for x in range(0, X+1):
            j = 0
            while x - j * A[i] >= 0:
                if dp[i][x - j * A[i]]:
                    dp[i+1][x] = True
                j += 1
    return 1 if dp[NA][X] else 0
    
if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print("%d" % output)


### FIXED CODE ###

import math

def read():
    X = int(input().strip())
    return X,


def solve(X):
    if X >= 2000:
        return 1
    A = [100 ,101, 102, 103, 104, 105]
    NA = 6
    dp = [[False for j in range(X+1)] for i in range(NA+1)]
    for i in range(NA+1):
        dp[i][0] = True
    for i in range(NA):
        for x in range(0, X+1):
            j = 0
            while x - j * A[i] >= 0:
                if dp[i][x - j * A[i]]:
                    dp[i+1][x] = True
                j += 1
    return 1 if dp[NA][X] else 0
    
if __name__ == '__main__':
    inputs = read()
    output = solve(*inputs)
    print("%d" % output)
### BUGGY CODE ###

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

n,q = map(int,input().split())
graph = [[] for _ in range(n)]
point = [0]*n
for i in range(n-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
for _ in range(q):
    a,b = map(int,input().split())
    a = a -1
    point[a]+=b
def dfs(now, prev = -1):
    for next in graph[now]:
        if next == prev:
            continue
        point[next] += point[now]
        dfs(next, now)
dfs(0)
print(*point)

### FIXED CODE ###

n,q = map(int,input().split())
graph = [[] for _ in range(n)]
point = [0]*n
for i in range(n-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
for _ in range(q):
    a,b = map(int,input().split())
    a = a -1
    point[a]+=b
stack = [];
stack.append(0)
visited = [False]*n
while stack:
    x = stack.pop()
    visited[x] = True
    for y in graph[x]:
        if visited[y] == False:
            point[y] += point[x]
            stack.append(y)
print(*point)
### BUGGY CODE ###

h, w, m = map(int, input().split())
targets = []
targets_count_tate = [0]*w
targets_count_yoko = [0]*h
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_tate[x] += 1
    targets_count_yoko[y] += 1
    targets.append((y, x))


ans = 0
for y in range(h):
    for x in range(w):
        res = targets_count_tate[x] + targets_count_yoko[y]
        if (y, x) in targets:
            res -= 1
        ans = max(ans, res)

print(ans)


### FIXED CODE ###

from collections import defaultdict
h, w, m = map(int, input().split())
targets = defaultdict(int)
targets_count_yoko = defaultdict(int)
targets_count_tate = defaultdict(int)
for _ in range(m):
    y, x = map(int, input().split())
    y -= 1
    x -= 1
    targets_count_yoko[x] += 1
    targets_count_tate[y] += 1
    targets[(y, x)] = -1

max_row = max(targets_count_yoko.values())
max_line = max(targets_count_tate.values())
y_idx = defaultdict(bool)
x_idx = defaultdict(bool)
max_count_x = 0
max_count_y = 0
for i in range(w):
    if targets_count_yoko[i] == max_row:
        x_idx[i] = True
        max_count_x += 1
for i in range(h):
    if targets_count_tate[i] == max_line:
        y_idx[i] = True
        max_count_y += 1


ans = max_line + max_row
kumi = max_count_x*max_count_y
for key_y, key_x in targets.keys():
    if y_idx[key_y] and x_idx[key_x]:
        kumi -= 1
    if kumi == 0:
        break

if kumi == 0:
    print(ans-1)
else:
    print(ans)
### BUGGY CODE ###

S = input()
n = len(S)
mod = 10**9 + 7
pow10 = [1]
for i in range(1,n):
    x = pow10[-1]
    y = 10*x%13
    pow10.append(y)
dp = [[0 for i in range(13)]for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    d = S[-i-1]
    if d == '?':
        for j in range(10):
            s = (pow10[i]*j)%13
            for t in range(13):
                r = (s+t)%13
                dp[i+1][r] = (dp[i+1][r] + dp[i][t])%mod
    else:
        j = int(d)
        s = (pow10[i]*j)%13
        for t in range(13):
            r = (s+t)%13
            dp[i+1][r] = (dp[i+1][r] + dp[i][t])%mod
print(dp[n][5])

### FIXED CODE ###

S = input()
n = len(S)
mod = 10**9 + 7
pow10 = [1]
for i in range(1,n):
    x = pow10[-1]
    y = 10*x%13
    pow10.append(y)
dp = [[0 for i in range(13)]for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    d = S[-i-1]
    if d == '?':
        for j in range(10):
            s = (pow10[i]*j)%13
            for t in range(13):
                r = (s+t)%13
                dp[i+1][r] = (dp[i+1][r] + dp[i][t])%mod
    else:
        j = int(d)
        s = (pow10[i]*j)%13
        for t in range(13):
            r = (s+t)%13
            dp[i+1][r] = (dp[i+1][r] + dp[i][t])%mod
print(dp[n][5])
### BUGGY CODE ###

def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  xmod=[y%m for y in x]
  from collections import Counter
  cx=dict(Counter(xmod))
  keys=list(cx.keys())
  ans1,ans2=0,0 # m倍になるペア、同数のペア
  d2={}
  for k in keys:
    if k==0:
      ans1+=cx[k]//2
      cx[k]-=2*(cx[k]//2)
    else:
      if k==m-k:
        ans1+=cx[k]//2
        cx[k]-=2*(cx[k]//2)
      elif m-k in keys:
        tmp=min(cx[k],cx[m-k])
        ans1+=tmp
        cx[k]-=tmp
        cx[m-k]-=tmp
      if cx[k]>=2:
        ans2+=cx[k]//2
        d2[k]=cx[k]//2
  d1={}
  for y in x:
    if y%m in d1:
      d1[y%m].append(y)
    else:
      d1[y%m]=[y]
  d3={}
  for k in d1:
    tmp={}
    d3[k]=0
    for i in d1[k]:
      if i in tmp:
        tmp[i]+=1
        if tmp[i]%2==0:
          d3[k]+=1
      else:
        tmp[i]=1
  for k in d2:
    tmp=d3[k]
    if tmp>=d2[k]:
      pass
    else:
      ans2-=d2[k]
      ans2+=tmp
  print(ans1+ans2)
if __name__=='__main__':
  main()



### FIXED CODE ###

def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  #xmod=[y%m for y in x]
  from collections import Counter
  cx=Counter(x)
  cxmod={}
  for k in cx:
    if k%m in cxmod:
      cxmod[k%m]+=cx[k]
    else:
      cxmod[k%m]=cx[k]
  keys=cxmod.keys()
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in keys:
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in keys:
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

  print(ans1+ans2)
if __name__=='__main__':
  main()
### BUGGY CODE ###

a,b=map(int,input().split())
if a==b:
    print(a)
else:
    s=0
    t=0
    for i in range(41):
        if 2**i>a:
            s=i
            break
    for i in range(41):
        if 2**i>b:
            t=i-1
            break
    ans=0
    for j in range(a,2**s):
        ans=ans^j
    for j in range(2**t,b+1):
        ans=ans^j
    print(ans)


### FIXED CODE ###

a,b=map(int,input().split())
if a==b:
    print(a)
else:
    s=4-a%4
    t=(1+b%4)
    ans=0
    for j in range(a,a+s):
        ans=ans^j
    for j in range(b+1-t,b+1):
        ans=ans^j
    print(ans)
### BUGGY CODE ###

import sys
import bisect
sys.setrecursionlimit(10 ** 9)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

_, M = lr()
A = lr()

A.sort()
for m in range(M):
    a = A[-1] // 2
    i = bisect.bisect_left(A, a)
    A.insert(i, a)
    A = A[:-1]
print(sum(A))


### FIXED CODE ###

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

import heapq
n, m = lr()
a = list(map(lambda x: - int(x), input().split()))
heapq.heapify(a)
for i in range(m):
    b = heapq.heappop(a) * (-1)
    b //= 2
    heapq.heappush(a, -b)
print(-sum(a))
### BUGGY CODE ###

def solve():
    N,K = map(int , input().split())
    A = list(map(int , input().split()))
    max_A = max(A)
    total = sum(A)
    # ave_region = total//N

    max_d = 1
    for d in A:
        if all(a%d==0 for a in A) and d > max_d:
            max_d = d
    if K >= total:
        max_d = total
    search_region = range(max_d, min(total, max_A+K)+1)
    
    for d in search_region:
        if total % d == 0:
            remainders = [a%d for a in A]
            remainders = sorted(remainders)
            # print(d, remainders)
            positive_rem = 0
            negative_rem = 0
            flag = True
            for rem in remainders:
                if positive_rem+rem <= K:
                    positive_rem += rem
                elif negative_rem+(d-rem) <=K:
                    negative_rem += (d-rem)
                else: 
                    flag = False
                    break

            if flag :
                # print(d, remainders, positive_rem, negative_rem)
                max_d = d
            
    print(max_d)
    
solve()

### FIXED CODE ###

def solve():
    N,K = map(int , input().split())
    A = list(map(int , input().split()))
    max_total = 22361 # sqrt(10**6 * 500)
    total = sum(A)
    search_space = set([])

    max_d = 1
    for d in range(1, min(total, max_total) ):
        if total % d == 0:
            search_space.add(d)
            search_space.add(total // d)
    
    # print(search_space)
    
    for d in search_space:
        if total % d == 0:
            remainders = [a%d for a in A]
            remainders = sorted(remainders)
            # print(d, remainders)
            positive_rem = 0
            negative_rem = 0
            flag = True
            for rem in remainders:
                if positive_rem+rem <= K:
                    positive_rem += rem
                elif negative_rem+(d-rem) <=K:
                    negative_rem += (d-rem)
                else: 
                    flag = False
                    break

            if flag and d > max_d:
                # print(d, remainders, positive_rem, negative_rem)
                max_d = d
            
    print(max_d)
    
solve()