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

K = int(input())

ans = -1
num7 = 7
if K%2 != 0:
    for i in range(100000):
        if (num7 % K) == 0:
            ans = i+1
            break
        else:
            num7 = num7*10+7
            i+=1

print(ans)

### FIXED CODE ###

K = int(input())

ans = -1
num7 = 7

for i in range(1000000):
    if (num7 % K) == 0:
        ans = i+1
        break
    else:
        num7 = (num7*10+7)%K
        i+=1

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

K = int(input())
valSum = 0

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

for A in range(1,K+1):
    for B in range(1,K+1):
        for C in range(1,K+1):
            valSum = origcd(origcd(A,B),C) + valSum

print(valSum)



### FIXED CODE ###

from math import gcd

K = int(input())
valSum = 0

for A in range(1,K+1):
    for B in range(1,K+1):
        for C in range(1,K+1):
            valSum += gcd(gcd(A,B),C)

print(valSum)
### BUGGY CODE ###

n = int(input())
a_list = [int(x) for x in input().split()]
b = []
for a in a_list:
    b.append(a)
    b = list(reversed(b))
print(*b)

### FIXED CODE ###

from collections import deque
n = int(input())
a_list = [int(x) for x in input().split()]
left_flag = n % 2 == 1
d = deque()
for a in a_list:
    if left_flag:
        d.appendleft(a)
    else:
        d.append(a)
    left_flag = not left_flag
print(*d)
### BUGGY CODE ###

from collections import deque

def main():
    h, w = map(int, input().split())
    ls = [input() for _ in range(h)]

    def trans(a, b):
        return a * w + b

    ls2 = [[] for _ in range(h * w)]

    for i in range(h):
        for j in range(w):
            # check ij
            if ls[i][j] == '#':
                continue
            if i >= 1 and ls[i-1][j] != '#':
                ls2[trans(i, j)].append(trans(i-1, j))
            if i <= h-2 and ls[i+1][j] != '#':
                ls2[trans(i, j)].append(trans(i + 1, j))
            if j <= w-2 and ls[i][j+1] != '#':
                ls2[trans(i, j)].append(trans(i, j + 1))
            if j >= 1 and ls[i][j-1] != '#':
                ls2[trans(i, j)].append(trans(i, j - 1))


    #print(ls2)


    def route(i, j):
        count = 1
        ss = deque(ls2[i])
        next = deque()
        explored = {i}
        while True:
            if not ss:
                count +=1
                ss = next
                next = deque()
            now =ss.popleft()
            if now in explored:
                continue
            if now == j:
                return count
            else:
                explored.add(now)
                next.extend(ls2[now])
    ans = 0
    for i in range(h * w - 1):
        if ls2[i] == []:
            continue
        for j in range(i+1, h * w):
            if ls2[j] == []:
                continue
            else:
                ans = max(ans, route(i, j))
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

def main():
    h, w = map(int, input().split())
    ls = [input() for _ in range(h)]

    def trans(a, b):
        return a * w + b

    ls2 = [[] for _ in range(h * w)]

    for i in range(h):
        for j in range(w):
            # check ij
            if ls[i][j] == '#':
                continue
            if i >= 1 and ls[i-1][j] != '#':
                ls2[trans(i, j)].append(trans(i-1, j))
            if i <= h-2 and ls[i+1][j] != '#':
                ls2[trans(i, j)].append(trans(i + 1, j))
            if j <= w-2 and ls[i][j+1] != '#':
                ls2[trans(i, j)].append(trans(i, j + 1))
            if j >= 1 and ls[i][j-1] != '#':
                ls2[trans(i, j)].append(trans(i, j - 1))


    #print(ls2)


    def route(i):
        count = 1
        ss = deque(ls2[i])
        next = deque()
        explored = {i}
        while ss or next:
            if not ss:
                count +=1
                ss = next
                next = deque()
            now =ss.popleft()
            if now in explored:
                continue
            else:
                explored.add(now)
                next.extend(ls2[now])
        return count-1
    ans = 0
    for i in range(h * w - 1):
        if ls2[i] == []:
            continue
        ans = max(ans, route(i))

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

import numpy as np
N = int(input())
a = [int(input()) for i in range(N)]
max_a = np.max(a)
for i in range(N):
    if a[i] != max_a:
        print(max_a)
    else:
#         print(i)
#         print(a[0:i]+a[i+1:])
        premax_a = np.max(a[0:i]+a[i+1:]) 
        print(premax_a)

### FIXED CODE ###

import numpy as np
N = int(input())
a = [int(input()) for i in range(N)]

# a = np.array(a)
max_a = np.max(a)
premax_a = np.sort(a)[::-1][1]

for i in range(N):
    if a[i] == max_a:
        print(premax_a)
    else:
        print(max_a)
### BUGGY CODE ###

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

key_set = None
for _ in range(m):
    l, r = [int(x) for x in input().split()]
    if not key_set:
        key_set = set(range(l, r + 1))
    else:
        key_set &= set(range(l, r + 1))
print(len(key_set))

### FIXED CODE ###

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

l_list = [0] * m
r_list = [0] * m
for i in range(m):
    l_list[i], r_list[i] = [int(x) for x in input().split()]

print(max(min(r_list) - max(l_list) + 1, 0))
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))

for i in range(k):
  max_h = max(h)
  h[h.index(max_h)] = 0
  
sum_h = sum(h)
if(sum_h == 0):
  print(0)
else:
  print(sum_h)

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
ans = 0

if(n <= k):
  print(0)
else:
  h.sort()
  a = []
  a = h[:n-k]
  print(sum(a))
### BUGGY CODE ###

def main():
    import numpy as np
    c=np.concatenate
    n=int(input())
    s=np.array([np.array(list(input())) for _ in [0]*n])
    cnt=0
    for a in range(n):
        for i in range(n):
            ia_n=(i+a)%n
            if not (c([s[i,i+a:n],s[i,:a]])==c([s[i:n-a,ia_n],s[n-a:n,ia_n]])).all():
                break
        else:
            cnt+=1
    print(n*cnt)
main()

### FIXED CODE ###

def main():
    n=int(input())
    nn=2*n-1
    s=[input() for _ in [0]*n]
    s=[i+i[:-1] for i in s]+[i+i[:-1] for i in s][:-1]
    ans=[[0]*n for _ in [0]*n]
    for i in range(1,nn):
        m=min(i+1,n)
        for j in range(nn-1):
            for k in range(max(i-j-n,0)+1,min(m,nn-j,i-j+n)):
                ii=i-k
                if s[i][j]!=s[ii][j+k]:
                    l=min(n-k+1,ii,j)
                    width=l-max(-1,ii-n,j-n)
                    ans[ii-l][j-l]=max(ans[ii-l][j-l],width)
    for i in range(1,n):
        for j in range(1,n):
            ans[i][j]=max(ans[i][j],ans[i-1][j-1]-1)
    print(sum([sum([i==0 for i in a]) for a in ans]))
main()
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
h = np.array(list(map(int, input().split())))
dp = np.zeros(n)
get_d = lambda i, d: d[i] if i >= 0 else 0
for i in list(range(n))[1:]:
    dp[i] = np.min([get_d(i-ki-1, dp)+np.abs(h[i]-get_d(i-ki-1, h)) for ki in range(k)])
print(int(dp[-1]))

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*n
for i in list(range(n))[1:]:
    tmp = max(0, i-k)
    dp[i] = min([dpk+abs(h[i]-hk) for dpk, hk in zip(dp[tmp:i], h[tmp:i])])
print(dp[-1])
### BUGGY CODE ###

import collections

N = int(input())

a = list()

for i in range(N):
    S = input()
    a.append(S)

c = collections.Counter(a)

#print(c.most_common()[0][1])

b =list()

for i in range(len(c)):
    if(int(c.most_common()[0][1]) == int(c.most_common()[i][1])):
        b.append(c.most_common()[i][0])

b.sort()

for i in range(len(b)):
    print(b[i])

### FIXED CODE ###

from collections import*
_,*s=open(0)
c=Counter(s).most_common()
print(*sorted(a*(b==c[0][1])for a,b in c))
### BUGGY CODE ###

a,b,c = map(int,input().split())
ans = 0
while True:
  if c > 0 and b > 0:
    ans += 2
    c -= 1
    b -= 1
  elif c > 0 and a > 0:
    ans += 1
    c -= 1
    a -= 1
  elif c > 0:
    print(ans+1)
    quit()
  elif c == 0:
    print(ans + b)
    quit()

### FIXED CODE ###

a,b,c = map(int,input().split())
ans = 0
if a+b > c-2:
  print(b+c)
else:
  print(a+2*b+1)
### BUGGY CODE ###

n = int(input())
alist = list(map(int, input().split()))
cnt = 0
for i in range(n):
    a = alist[:i] + alist[i+1:]
    if all(alist[i]%a[j] for j in range(n-1)):
        cnt += 1
print(cnt)



### FIXED CODE ###

from collections import Counter 
n = int(input())
a = list(map(int, input().split()))
s = set(a)
c = Counter(a)
t = [0] * (10**6 + 1)
for i in s:
    for j in range(i, 10**6+1, i):
        t[j] += 1

ans = len([1 for i in s if t[i] == 1 and c[i] == 1])
print(ans)
### BUGGY CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
mxa=max(a)

def get_sieve_of_eratosthenes(mxa):
    fact = [0]*(mxa+1)
    limit = int(math.sqrt(mxa))
    for i in range(2,limit+1):
        if fact[i]!=0:
            continue
        else:
            fact[i]=i
            for j in range(i, mxa+1, i):
                if fact[j]==0:
                    fact[j]=i
    for i in range(2,mxa+1):
        if fact[i]==0:
            fact[i]=i

    return fact

fact = get_sieve_of_eratosthenes(mxa)

lst=[0]*(len(fact))
for i in range(n):
    divisor = set()
    while a[i]!=1:
        divisor.add(fact[a[i]])
        a[i]//=fact[a[i]]
    for d in divisor:
        lst[d]+=1

pair=True
st=True

for i in lst:
    if i>=2:
        pair=False
    if i==n:
        st=False
if pair:
    print("pairwise coprime")
elif st:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
mxa=max(a)

def get_sieve_of_eratosthenes(mxa):
    fact = [0]*(mxa+1)
    limit = int(math.sqrt(mxa))
    for i in range(2,limit+1):
        if fact[i]!=0:
            continue
        else:
            fact[i]=i
            for j in range(i, mxa+1, i):
                if fact[j]==0:
                    fact[j]=i
    for i in range(2,mxa+1):
        if fact[i]==0:
            fact[i]=i

    return fact

fact = get_sieve_of_eratosthenes(mxa)

lst=[0]*(len(fact))
for i in range(n):
    divisor = set()
    while a[i]!=1:
        divisor.add(fact[a[i]])
        a[i]//=fact[a[i]]
    for d in divisor:
        lst[d]+=1

pair=True
st=True

for i in lst:
    if i>=2:
        pair=False
    if i==n:
        st=False
if pair:
    print("pairwise coprime")
elif st:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

from collections import defaultdict


def prime_decomposition(n):
    table = defaultdict(int)
    # table = [0] * (n + 1)

    i = 2
    while n % i == 0:
        n //= i
        table[i] += 1

    i = 3
    while i * i <= n:
        while n % i == 0:
            n //= i
            table[i] += 1
        i += 2

    if n > 1:
        table[n] += 1

    return table


def main():
    mod = 10 ** 9 + 7

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

    t = [prime_decomposition(x) for x in a]

    lcm_d = defaultdict(int)
    for pd in t:
        for prime, power in pd.items():
            lcm_d[prime] = max(lcm_d[prime], power)

    gcd_d = defaultdict(lambda: mod - 1)
    for pd in t:
        for prime, power in lcm_d.items():
            pd[prime] = power - pd[prime]
            gcd_d[prime] = min(pd[prime], gcd_d[prime])

    gcd_ = 1
    for prime, power in gcd_d.items():
        gcd_ = (gcd_ * pow(prime, power, mod)) % mod

    ret = 0
    for pd in t:
        curr = 1
        for prime, power in pd.items():
            curr = (curr * pow(prime, power - gcd_d[prime], mod)) % mod
        ret = (ret + curr) % mod

    ret = ret * gcd_ % mod

    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from functools import reduce

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

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

    mod = 10 ** 9 + 7

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

    L = reduce(lcm, a)

    ret = 0
    for x in a:
        ret = (ret + pow(x, mod - 2, mod)) % mod
    ret = ret * L % mod
    print(ret)


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

N=int(input())

R=[[] for i in range(N)]

for i in range(N-1):
    a,b,c=map(int,input().split())
    R[a-1].append([b-1,c])
    R[b-1].append([a-1,c])

Q,K=map(int,input().split())
C=[0]*N
stack=[]
for i in range(N):
    if i==K-1:
        C[i]=0
    else:
        chk = [0] * N
        stack=[[K-1,i,0]]
        f=True
        while stack:
            if f==False:
                break
            s,g,d=stack.pop()
            chk[s]=1
            for j,c in R[s]:
                if chk[j]==1:continue
                if j==g:
                    C[i]=d+c
                    f=False
                    break
                else:
                    stack.append([j,g,d+c])

for i in range(Q):
    x,y=map(int,input().split())
    print(C[x-1]+C[y-1])



### FIXED CODE ###

N=int(input())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b,c=map(int,input().split())
    G[a-1].append([b-1,c])
    G[b-1].append([a-1,c])

Q,K=map(int,input().split())

SD=[0]*N
seen=[0]*N
stack=[]
stack.append([K-1,0])
seen[K-1]=1
while stack:
    x,d=stack.pop()
    for y,d0 in G[x]:
        if seen[y]==0:
            SD[y]=d+d0
            stack.append([y,d+d0])
            seen[y]=1
for i in range(Q):
    x,y=map(int,input().split())
    ans=SD[x-1]+SD[y-1]
    print(ans)
### BUGGY CODE ###

import math
 
N, M = list(map(int,input().split()))
 
d = int(M/N)
 
if M%N == 0:
	print(d)
else: 
	i = 0
	while True:
		if M%(N+i+1) == 0:
			print(int(M/(N+i+1)))
			break
		i += 1

### FIXED CODE ###

import math, sys, random

N, M = list(map(int,input().split()))
# N, M = 1111, 1000000000

def is_prime(n):
    if n == 2: return True
    if n == 1 or n & 1 == 0: return False

    d = (n - 1) >> 1
    while d & 1 == 0:
        d >>= 1

    for k in range(100):
        a = random.randint(1, n - 1)
        t = d
        y = pow(a, t, n)

        while t != n - 1 and y != 1 and y != n - 1:
            y = (y * y) % n
            t <<= 1

        if y != n - 1 and t & 1 == 0:
            return False

    return True

d = int(math.floor(M/N))

if M%N == 0:
	print(d)
	sys.exit()

i = 0
f = False
while True:
	if M%(N+i+1) == 0:
		print(int(M/(N+i+1)))
		sys.exit()
	i += 1
	if i == 100000 and is_prime(M):
		print(1)
		sys.exit()
### BUGGY CODE ###

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

ans = 10**18
for i in range(N-K+1):
    y = x[i:i+K]
    if y[0] < 0 and y[K-1] < 0:
        ans = min(ans, abs(y[0]))
    elif y[0] <= 0 and 0 <= y[K-1]:
        ans = min(ans, y[K-1]-2*y[0], 2*y[K-1]-y[0])
    else:
        ans = min(ans, y[K-1])

print(ans)


### FIXED CODE ###

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

ans = 10**18
for i in range(N-K+1):
    y0 = x[i]
    yk = x[i+K-1]
    if yk < 0:
        ans = min(ans, abs(y0))
    elif y0 <= 0 and 0 <= yk:
        ans = min(ans, yk-2*y0, 2*yk-y0)
    else:
        ans = min(ans, yk)

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

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

a_list.sort(reverse=True)
b_list.sort(reverse=True)
a_list.append(-1)
b_list.append(-1)
ans = 1
a_i = 0
b_i = 0
for i in range(N*M, 0, -1):
    if i == a_list[a_i] and i == b_list[b_i]:
        a_i += 1
        b_i += 1
    elif i == a_list[a_i]:
        a_i += 1
        ans *= b_i 
    elif i == b_list[b_i]:
        b_i += 1
        ans *= a_i 
    else:
        ans *= (a_i*b_i - (N * M - i)) 
print(ans % mod)



### FIXED CODE ###

N, M = map(int, input().split())
a_list = tuple(map(int, input().split()))
b_list = tuple(map(int, input().split()))
mod = 10 ** 9 + 7

a_list = sorted(a_list, reverse=True)
b_list = sorted(b_list, reverse=True)
a_list.append(-1)
b_list.append(-1)
ans = 1
a_i = 0
b_i = 0
for i in range(N*M, 0, -1):
    if i == a_list[a_i] and i == b_list[b_i]:
        a_i += 1
        b_i += 1
    elif i == a_list[a_i]:
        a_i += 1
        ans *= b_i
        ans %= mod
    elif i == b_list[b_i]:
        b_i += 1
        ans *= a_i
        ans %= mod
    else:
        ans *= (a_i*b_i - (N * M - i))
        ans %= mod
print(ans % mod)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
result=1
a.sort()
if a[0]==0:
    print(0)
    exit(0)
for i in range(n//2):
    result=result*a[i]*a[n-i-1]
if n%2==1:
    result*=a[n//2+1]
if result==1000000000000000000:
    print(result)
elif 18< len(str(result)):
    print(-1)
else:
    print(result)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
result=1
for i in a:
    result*=i
    if 10**18<result:
        result=-1
        break
print(result)
### BUGGY CODE ###

data = []
i = int(input())

data = [int(input()) for _n in range(i)]
maxInt = max(data)
for n in range(i):
	if maxInt != data[n]:
		print(maxInt)
	else:
		print(max(data[0:n]+data[n+1:]))

### FIXED CODE ###

import copy

data = []
i = int(input())

data = [int(input()) for _n in range(i)]
maxInt = max(data)
data2 = copy.copy(data)
data2.remove(maxInt)
max2Int = max(data2)
for n in range(i):
	if maxInt != data[n]:
		print(maxInt)
	else:
		print(max2Int)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    d = [[10**9]*N for _ in range(N)]

    for i in range(N):
        d[i][i] = 0
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)
                d[i][j] = 1
                d[j][i] = 1
    
    # ２部グラフ 判定
    stack = [(0,1)]
    color = [-1]*N

    while stack:
        node,c = stack.pop()
        color[node] = c

        for next in matrix[node]:
            if color[next] == -1:
                stack.append((next,~c))
            else:
                if c^color[next] == 0:
                    print(-1)
                    return


    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(answer+1)
    return

def main():
    N = int(input())
    S = [input() for _ in range(N)]
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

def solve(N: int, S: "List[str]"):
    matrix = [[] for _ in range(N)]
    d = [[10**5]*N for _ in range(N)]

    for i in range(N):
        d[i][i] = 0
        for j in range(N):
            if S[i][j] == "1":
                matrix[i].append(j)
                d[i][j] = 1
                d[j][i] = 1
    
    # ２部グラフ 判定
    stack = [(0,1)]
    color = [-1]*N

    while stack:
        node,c = stack.pop()
        color[node] = c

        for next in matrix[node]:
            if color[next] == -1:
                stack.append((next,~c))
            else:
                if c^color[next] == 0:
                    print(-1)
                    return


    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    answer = 0
    for i in range(N):
        answer = max(answer,max(d[i]))
    print(answer+1)
    return

def main():
    N = int(input())
    S = [input() for _ in range(N)]
    solve(N, S)

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

from collections import Counter

def Comb(n,k):
    comb_ans=1
    for i in range(1,k+1):
        comb_ans*=(n-i+1)/i
    comb_ans=int(comb_ans)
    return comb_ans

N=int(input())
A=list(map(int,input().split()))
C=Counter(A)
ans=0
L=[0]*N
for i in range(N):
    L[A[i]-1]+=1
for i in range(len(C)):
    ans+=Comb(C.most_common()[i][1],2)
for i in range(N):
    pri=ans
    pri=ans-Comb(L[A[i]-1],2)+Comb(L[A[i]-1]-1,2)
    print(pri)


### FIXED CODE ###

from collections import Counter

def Comb(n,k):
    comb_ans=1
    for i in range(1,k+1):
        comb_ans*=(n-i+1)/i
    comb_ans=int(comb_ans)
    return comb_ans

N=int(input())
A=list(map(int,input().split()))
C=Counter()
C.update(A)
ans=0
L=[0]*N
for i in range(N):
    L[A[i]-1]+=1
Most=C.most_common()
#print(Most)
for i in range(len(C)):
    ans+=Comb(Most[i][1],2)
for i in range(N):
    pri=ans
    pri=ans-L[A[i]-1]+1
    print(pri)
### BUGGY CODE ###

import sys
import heapq

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

alist.sort()
flist.sort(reverse=True)
#print(alist)
#print(flist)

if sum(alist)<=K:
  print(0)
  sys.exit(0)
  
hq=[]
for i in range(N):
  heapq.heappush(hq,(-alist[i]*flist[i],alist[i],flist[i]))
  
for i in range(K):
  naf,a,f=heapq.heappop(hq)
  naf+=f
  a-=1
  if a>0:
    heapq.heappush(hq,(naf,a,f))
    
if len(hq)==0:
  print(0)
else:
  naf,a,f=heapq.heappop(hq)
  print(-naf)

### FIXED CODE ###

import sys
N,K=map(int,input().split())
alist=list(map(int,input().split()))
flist=list(map(int,input().split()))
alist.sort()
flist.sort(reverse=True)
#print(alist)
#print(flist)

def check(m):
  cnt=0
  for i in range(N):
    if alist[i]*flist[i]>m:
      cnt+=-(-(alist[i]*flist[i]-m)//flist[i])
  
  #print(m,cnt,K)
  if cnt<=K:
    return True
  else:
    return False

if sum(alist)<=K:
  print(0)
  sys.exit(0)

baseline=0
for i in range(N):
  baseline=max(baseline,alist[i]*flist[i])
#print(baseline)

l,r=0,baseline
while l<=r:
  mid=(l+r)//2
  #print(l,mid,r)
  if not check(mid-1) and check(mid):
    print(mid)
    break
  elif not check(mid):
    l=mid+1
  else:
    r=mid-1
### BUGGY CODE ###

import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, K = rl()
A = rl()

s = sum(A)
m = math.ceil(math.sqrt(s))

divs = set()
i = 1
while i < s:
	if s % i == 0:
		divs.add(i)
		divs.add(s//i)
	i += 1

ans = 1
for n in divs:
	B = [a % n for a in A]
	s = sum(B)
	if s % n != 0: continue
	B.sort()
	B = [b for b in B if b != 0]
	if len(B) == 0:
		ans = max(ans, n)
		continue
	bsum = [0]*len(B)
	rbsum = [0]*len(B)
	bs = 0
	for i, b in enumerate(B):
		bs += b
		bsum[i] = bs
	bs = 0
	for i, b in reversed(list(enumerate(B))):
		bs += n - b
		rbsum[i] = bs
	need = float('inf')
	for i in range(len(B)-1):
		if bsum[i] == rbsum[i+1]:
			need = bsum[i]
			break
	if need <= K:
		ans = max(ans, n)
print(ans)



### FIXED CODE ###

import sys, math
from collections import defaultdict
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

N, K = rl()
A = rl()

s = sum(A)
m = math.ceil(math.sqrt(s))

divs = []
divs2 = []
i = 1
while i <= m:
	if s % i == 0:
		divs.append(i)
		divs2.append(s//i)
	i += 1
divs.reverse()
divs2 += divs

ans = 1
for n in divs2:
	B = [a % n for a in A]
	s = sum(B)
	if s % n != 0: continue
	B.sort()
	B = [b for b in B if b != 0]
	if len(B) == 0:
		ans = max(ans, n)
		break
	bsum = [0]*len(B)
	rbsum = [0]*len(B)
	bs = 0
	for i, b in enumerate(B):
		bs += b
		bsum[i] = bs
	bs = 0
	for i in range(len(B)-1, -1, -1):
		bs += n - B[i]
		rbsum[i] = bs
	need = float('inf')
	for i in range(len(B)-1):
		if bsum[i] == rbsum[i+1]:
			need = bsum[i]
			break
	if need <= K:
		ans = max(ans, n)
		break
print(ans)