Problem:


Score : 500 points

Problem Statement

We have a sequence of N integers: A_1, A_2, \cdots, A_N.

You can perform the following operation between 0 and K times (inclusive):

Choose two integers i and j such that i \neq j, each between 1 and N (inclusive). Add 1 to A_i and -1 to A_j, possibly producing a negative element.

Compute the maximum possible positive integer that divides every element of A after the operations. Here a positive integer x divides an integer y if and only if there exists an integer z such that y = xz.

Constraints

2 \leq N \leq 500

1 \leq A_i \leq 10^6

0 \leq K \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \cdots A_{N-1} A_{N}

Output

Print the maximum possible positive integer that divides every element of A after the operations.

Sample Input 1

2 3
8 20

Sample Output 1

7

7 will divide every element of A if, for example, we perform the following operation:

Choose i = 2, j = 1. A becomes (7, 21).

We cannot reach the situation where 8 or greater integer divides every element of A.

Sample Input 2

2 10
3 5

Sample Output 2

8

Consider performing the following five operations:

Choose i = 2, j = 1. A becomes (2, 6).

Choose i = 2, j = 1. A becomes (1, 7).

Choose i = 2, j = 1. A becomes (0, 8).

Choose i = 2, j = 1. A becomes (-1, 9).

Choose i = 1, j = 2. A becomes (0, 8).

Then, 0 = 8 \times 0 and 8 = 8 \times 1, so 8 divides every element of A. We cannot reach the situation where 9 or greater integer divides every element of A.

Sample Input 3

4 5
10 1 2 22

Sample Output 3

7

Sample Input 4

8 7
1 7 5 6 8 2 6 5

Sample Output 4

5



Sample input:
2 3
8 20


Sample output:
7

Submission status: Runtime Error

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

def get_divisors(n):
    divisors = []
    for num in range(ceil(n**0.5), n+1):
        if n % num == 0:
            divisors.append(n//num)
            if n//num != n:
                divisors.append(num)
    divisors.sort(reverse=True)
    return divisors

total = sum(A)
divisors = get_divisors(total)
ans = -1
for d in divisors:
    R = [a%d for a in A]
    R.sort(reverse=True)
    pr = 0
    nr = -sum(R)
    for i, r in enumerate(R):
        pr += d-r
        nr += r
        if nr+pr >= 0:
            if pr <= K and nr+pr == 0:
                ans = d
            break
    if ans != -1:
        print(ans)
        break
else:
    print(1)

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse = True)
    return divisors
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = sum(A)
divisors = make_divisors(m)
for d in divisors:
    A1 = list(map(lambda x:x%d, A))
    A1.sort()
    res = 0
    for i in range(N):
        res+=A1[i]
        if res>K:
            res-=A1[i]
            index = i+1
            break
    res1 = 0
    for i in range(index, N):
        res1+=d-A1[i]
    if res>=res1:
        ans = d
        break
print(ans)

Submission status: Runtime Error

Solution code:
N,K=map(int, input().split())
A=[int(i) for i in input().split()]
s=sum(A)
yakusu=[]
for i in range(1,s):
    if s%i==0:
        yakusu.append(i)
    else:
    pass
B=[[] for i in len(yakusu)]
d=[1]
for i in range(len()):
    for j in range(len(A)):
        b=A[j]%yakusu[i]
        B[i].append(b)
    if sum(B[i])%yakusu[i]==0:
        d.append(yakusu[i])
print(max(d))

Submission status: Runtime Error

Solution code:
N,K=map(int, input().split())
A=[int(i) for i in input().split()]
s=sum(A)
yakusu=[]
for i in range(1,s):
  if s%i==0:
    yakusu.append(i)
  else:
    pass
yakusu.reversed()
B=[]
d=[1]
for i in range(len(yakusu)):
  B[i]=[]
  for j in range(len(A)):
    b=A[j]%yakusu[i]
    B[i].append(b)
  if sum(B[i])%yakusu[i]==0:
    d.append(yakusu[i])
print(max(d))

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

def checker(A,k):
    if sum(costs[sum(A) // d:]) <= k:
        return True
    return False

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

for d in make_divisors(sum(A)):
    buf = []
    if d == 1:
        print(d)
        break
    else:
        for a in A:
            buf.append(a%d)
        print(buf)
        if checker(buf,k):
            print(d)
            break

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

def checker(A,k):
    if sum(sorted(A)[:-1]) <= k:
        return True
    return False

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

for d in make_divisors(sum(A)):
    buf = []
    buf2 = []
    if d == 1:
        print(d)
        break
    else:
        for a in A:
            buf.append(a%d)
        #print(buf)
        if checker(buf.sort(reverse=True),k):
            print(d)
            break

Submission status: Runtime Error

Solution code:
def input():
  return sys.stdin.readline()[:-1]

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)

  divisors.sort(reverse=True)
  return divisors

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

sumA = sum(A)
kouho = make_divisors(sumA)

for i in kouho:
  if sumA%i != 0:
    continue
  r = [0]*N
  for j in range(N):
    r[j] = A[j]%i
  sumr = sum(r)
  if sumr%i != 0:
    continue
  r.sort(reverse=True)
  num = 0
  for k in range(sumr//i):
    num += i-r[k]
  if num <= K:
    print(i)
    exit()

Submission status: Runtime Error

Solution code:

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
A = list(map(int,input().split()))
 
def checker(n,A):
    sm = 0
    for i in range(N):
        A[i] = A[i]%n
        sm += A[i]
    if sm <= 2*K and sm%n == 0:
        return True
    else:
        return False
 
 
upper = min(2*K,sum(A))
ans = 1
sm = sum(A)
from math import sqrt
lis = []
for i in range(int(sqrt(sm))+1):
    if sm%i == 0:
        lis.append(i)
        lis.append(sm/i)
lis.sort(reverse=True)
for i in lis:
    tempA = A.copy()
    if checker(i,tempA):
        ans = i
        break
print(ans)

Submission status: Runtime Error

Solution code:
def yakusu(n):
    m=1
    re=[]
    while m**2<n:
        a,md=divmod(n,m)
        if md==0:
            re.append(m)
            re.append(a)
        m+=1
    if m**2==n:
        re.append(m)
    return re

n, k = map(int, input().split())
aa = list(map(int, input().split()))
yk = yakusu(sum(aa))
yk.sort(reverse=True)
for y in yk:
    rs=[a%y for a in aa if a%y]
    rs.sort()
    l=0
    sl=rs[0]
    r=len(rs)-1
    sr=y-rs[r]
    while 1:
        if l+1==r:
            if sl==sr and sl<=k:
                print(y)
                exit()
            else:
                break
        if sl>sr:
            r-=1
            sr+=y-rs[r]
            if sr>k:break
        else:
            l+=1
            sl+=rs[l]
            if sl>k:break
print(1)

Submission status: Runtime Error

Solution code:
import decimal,math
decimal.getcontext().prec = 100
def sum1(pre,l,r):
    l=max(l,0)
    if(l==0):
        return pre[r]
    return pre[r] - pre[l - 1]
abc=[]
def printDivisors(n) : 
    i = 1
    while i <= math.sqrt(n): 
          
        if (n % i == 0) : 
              
            if (n / i == i) : 
                abc.append(i) 
            else : 
                abc.append(i)
                abc.append(n/i)
        i = i + 1
n,k=map(int,raw_input().split())

arr=map(int,raw_input().split())
printDivisors(s)
abc.sort()
abc=abc[::-1]
ans=1
for i in abc:
    l=0
    flag=0
    c=[]
    for j in arr:
        c.append(j%i)
    c.sort()
    if(sum(c[:-sum(c)/i])<=k)
        print i
        exit()

Submission status: Runtime Error

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))

s = 2
l = [0]*n
maxs = 0
suma = sum(a)
while s < suma:
    if s > math.sqrt(suma):
        break
    if sum(a)%s == 0:
        for i in range(n):
            l[i] = a[i]%s
        l.sort()
        sml = sum(l)
        ns = sml//s
        if sml%s == 0 and -sum(l[len(l)-ns:len(l)])+ns*s<=k:
            maxs = s
        s = s + 1
    else:
        s = s + 1
print(maxs)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
from math import sqrt
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N,K=MAP()
A=LIST()

sm=sum(A)

def divisor_set(N: int) -> set:
    """ 約数の列挙・個数 """
    # 1とその数はデフォで入れとく
    s = {1, N}
    # 終点はルート切り捨て
    for i in range(2, int(sqrt(N))+1):
        # 割り切れるなら、iとN/iを追加
        if N % i == 0:
            s.add(i)
            s.add(N // i)
    return s

divs=sorted(divisor_set(sm), reverse=True)

for div in divs:
    B=[]
    for i in range(N):
        if A[i]%div!=0:
            B.append(A[i]%div)
    # mod取ったものをソート、これを前後からdivの約数に合わせていく
    B.sort()
    B=deque(B)
    cnt=0
    while len(B):
        # 先頭を引いていってdivの約数になるまでの距離
        dista=B[0]%div
        # 末尾を足していってdivの約数になるまでの距離
        distb=div-B[-1]%div
        # どちらが近いかに応じてリストBを操作する
        if dista>distb:
            B[0]-=distb
            B.pop()
            cnt+=distb
        elif dista<distb:
            B[-1]-=dista
            B.popleft()
            cnt+=dista
        elif dista==distb:
            B.pop()
            B.popleft()
            cnt+=dista
    # 操作回数がK回以内ならOK
    if cnt<=K:
        print(div)
        exit()

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
A=[int(i) for i in input().split()]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

#s=sum(A)

D=make_divisors(s)
D.sort()
D.reverse()
print(D)

for m in D:
    now=k
    P=[i%m for i in A]
    P.sort()
    for i in range(n):
        now-=P[i]
        if now<=0:
            now+=P[i]
            ck=i
            break
    else:
        print(m)
        break
    NP=[m-i for i in P]
    now=k
    for i in range(ck,n):
        now-=NP[i]
        if now<0:
            break
    else:
        print(m)
        break

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

N,K = map(int,input().split())
A = list(map(int,input().split()))
D = sum(A)
D = make_divisors(D)[::-1]

for d in D:
    a = []
    for i in range(N):
        a.append(A[i]%d)
    k = 0
    M = max(a)
    while k <= K and M != 0:
        i = 0
        j = 0
        m = d
        M = 0
        for l in range(N):
            if 0 < a[l] < m:
                m = a[l]
                i = l
        for l in range(N-1,-1,-1)
            if a[l] > M:
                M = a[l]
                j = l
        if m == d:
            break
        if m <= d-M:
            a[i] = 0
            a[j] += m
            a[j] %= d
            k += m
        else:
            a[i] -= d-M
            a[i] %= d
            a[j] = 0
            k += d-M
    if k <= K:
        break

print(d)

Submission status: Runtime Error

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

nums = A[:]

sum_n = sum(nums)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

divisors = sorted(list(make_divisors(sum_n)), reverse=True)
#print('DIV', divisors)


for d in divisors:
    mod_nums = list(map(lambda x: x%d, nums[:]))
    mod_nums = sorted(mod_nums)
    #print(mod_nums)
    x = 10**10
    for i in range(1, len(mod_nums)-1):
        if sum(mod_nums[:i]) == sum(list(map(lambda x: d-x, mod_nums[i:]))):
            x = sum(mod_nums[:i])
            break
    #print(d, x)
    if x <= K:
        ans = d
        break
            
        
        



print(ans)

Submission status: Runtime Error

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

def checker(n,A):
    sm = 0
    for i in range(N):
        A[i] = A[i]%n
        sm += A[i]
    if sm <= 2*K and sm%n == 0:
        return True
    else:
        return False


upper = min(2*K,sum(A))
ans = 1
sm = sum(A)
from math import sqrt
lis = []
for i in range(int(sqrt(sm))+1):
    if sm%i == 0:
        lis.append(i)
        lis.append(sm // i)
lis.sort(reverse=True)
for i in lis:
    tempA = A.copy()
    if checker(i,tempA):
        ans = i
        break
print(ans)

Submission status: Runtime Error

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
for i in range(max(a) + k +1):
  s = [x % i for x in a]
  if sum(s) % i == 0:
    print(i)
    break

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
a_list = list(map(int, input().split()))

def divisors(num):
    """
    約数全列挙
    """
    divisors = []
    for i in range(1, int(num ** 0.5) + 1):
        if num % i == 0:
            divisors.append(i)
            if i != num // i:
                divisors.append(num // i)

    return divisors
sum_num = sum(a_list)
a_list.sort()
div = divisors(sum_num)
div.sort(reverse=True)
ans = 1
from bisect import *
for d in div:
    plus = 0
    minus = 0
    mul = [-d]
    if d == 1:
        break
    for i in range(22):
        mul.append(d*i)
    for i, a in enumerate(a_list):
        if i != N-1:
            if a % d == 0:
                continue
            else:
                idx = bisect_left(mul, a)
                pp = mul[idx-1]
                p = mul[idx]
                n = mul[idx+1]
                v = min(abs(a-pp), abs(a-p), abs(a-n))

                if plus + v <= K and minus + v <= K:
                    for i in [pp, p, n]:
                        if abs(a-i) == v:
                            if i >= a:
                                plus += i - a
                            else:
                                minus += a -i
                else:
                    if plus + v >= K:
                        s = float("inf")
                        for i in [pp, p, n]:
                            if abs(a-i) != v:
                                s = min(s, abs(a-i))
                        minus += s
                    else:
                        s = float("inf")
                        for i in [pp, p, n]:
                            if abs(a-i) != v:
                                s = min(s, abs(a-i))
                        plus += s
        else:
            if plus == minus and a % d == 0:
                ans = max(ans, d)
                break
            else:
                if plus >= minus:
                    tmp = plus - minus
                    if plus > K :
                        continue
                    if (a + tmp) % d == 0:
                        ans = max(ans, d)
                        break
                else:
                    tmp = minus - plus
                    if minus > K:
                        continue
                    if (a + tmp) % d == 0:
                        ans = max(ans, d)
                        break
print(ans)

Submission status: Runtime Error

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

nums = A[:]

sum_n = sum(nums)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

divisors = sorted(list(make_divisors(sum_n)), reverse=True)
#print('DIV', divisors)


for d in divisors:
    mod_nums = list(map(lambda x: x%d, nums[:]))
    mod_nums = sorted(mod_nums)
    #print(mod_nums)
    x = 10**10
    for i in range(1, len(mod_nums)):
        if sum(mod_nums[:i]) == sum(list(map(lambda x: d-x, mod_nums[i:]))):
            x = sum(mod_nums[:i])
            break
    #print(d, x)
    if x <= K:
        ans = d
        break
            
        
        



print(ans)

Submission status: Runtime Error

Solution code:
import sys
import collections
import copy
import math
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(int(i) for i in input().split())
A_sum = sum(A)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    list.sort(divisors, reverse=True)
    return divisors
chk = make_divisors(A_sum)
flag = 0
for i in range(len(chk)):
    trial = chk[i]
    count = 0
    coll = trial
    count += A[0]%trial
    mod_list= [A[0]%trial]
    for j in range(1,N):
        count += A[j]%trial
        mod_list.append(A[j%trial])
    ans = count//trial
    list.sort(mod_list,reverse= True)
    test = 0
    for j in range(ans):
        test += trial-mod_list[i]
    if test > K :
        continue
    else:
        print(trial)
        break

Submission status: Runtime Error

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

def checker(n,A):
    sm = 0
    for i in range(N):
        A[i] = A[i]%n
        sm += A[i]
    if sm <= 2*K and sm%n == 0:
        return True
    else:
        return False
upper = min(2*K,sum(A))

for i in range(upper,max(-1,upper - 10**4),-1):
    tempA = A.copy()
    if checker(i,tempA):
        ans = i
        break
print(ans)

Submission status: Runtime Error

Solution code:
def main():

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    """convenient decorator
    # @functools.lru_cache():
    # to facilitate use of recursive function
        # ex:
        # from functools import lru_cache
        # import sys
        # sys.setrecursionlimit(10**9)
        # @lru_cache(maxsize=None)
        # def fib(n):
        #     if n < 2:
        #         return n
        #     return fib(n-1) + fib(n-2)
        # print(fib(1000))
    """
    
    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter #sort 
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    # first create factorial_list
    # fac_list = mod_factorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something
        >>  else:
        >>      do something
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array, use [[0] * N for _ in range(N)]
    # set inputs
        # put inputs between specific values (almost as quickly)
        # ex) S = [-INF] + [int(r()) for _ in range(A)] + [INF]
        # open(0).read() is sometimes useful:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions used
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    if __name__ != '__main__':
        # for test
        sys.stdin = open('sample.txt')
        
    # ----------------------------------
    # main

    N, K = R()
    A = R()
    A.sort(reverse=True)
    A_sub = [0] * N
    sumA = sum(A)
    
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)
        divisors.sort(reversed=True)
        return divisors
    
    divisors = make_divisors(sumA)
    for divisor in divisors:
        for i in range(N):
            A_sub[i] = A[i] % divisor
            A_sub.sort()
            A_sub_zero = A_sub.count(0)
            A_sub_total = (N-A_sub_zero) * divisor
            SUM_A_sub = sum(A_sub)
            UNDER_SUM_A = A_sub_total - SUM_A_sub
            k = 0
            count = 0
            for i in A_sub:
                A_sub_total = A_sub_total - i
                count += i
                UNDER_SUM_A -= abs(divisor-i)
                if i >= UNDER_SUM_A:
                    if k <= count:
                        print(divisor)
                        exit()
                    else:
                        break
        
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # three methods for loop: keys(), values(), items()
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    # to make binary digits text
    >>> a = 5
    >>> bin_str_a = format(a, '#06b')
    >>> print(bin_str_a)
    0b0101 # first 2 strings (='0b') indicates it is binary
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

def checker(n,A):
    sm = 0
    for i in range(N):
        A[i] = A[i]%n
        sm += A[i]
    if sm <= 2*K and sm%n == 0:
        return True
    else:
        return False
upper = min(2*K,sum(A))

for i in range(upper,max(-1,upper - 10**4),-1):
    tempA = A.copy()
    if checker(i,tempA):
        ans = i
        break
print(i)