Buggy python submission (verdict: Time Limit Exceeded):
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 submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
import math

def solve():
    N,K = map(int , input().split())
    A = list(map(int , input().split()))
    total = sum(A)
    max_a = max(A)
    search_region = min( total+1, N*max_a+1)
    
    max_d = 1
    for d in range(2, 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 submission:
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()