Vladimir wants to modernize partitions in his office. To make the office more comfortable he decided to remove a partition and plant several bamboos in a row. He thinks it would be nice if there are n bamboos in a row, and the i-th from the left is a_{i} meters high. 

Vladimir has just planted n bamboos in a row, each of which has height 0 meters right now, but they grow 1 meter each day. In order to make the partition nice Vladimir can cut each bamboo once at any height (no greater that the height of the bamboo), and then the bamboo will stop growing.

Vladimir wants to check the bamboos each d days (i.e. d days after he planted, then after 2d days and so on), and cut the bamboos that reached the required height. Vladimir wants the total length of bamboo parts he will cut off to be no greater than k meters.

What is the maximum value d he can choose so that he can achieve what he wants without cutting off more than k meters of bamboo?


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10^11) — the number of bamboos and the maximum total length of cut parts, in meters.

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the required heights of bamboos, in meters.


-----Output-----

Print a single integer — the maximum value of d such that Vladimir can reach his goal.


-----Examples-----
Input
3 4
1 3 5

Output
3

Input
3 40
10 30 50

Output
32



-----Note-----

In the first example Vladimir can check bamboos each 3 days. Then he will cut the first and the second bamboos after 3 days, and the third bamboo after 6 days. The total length of cut parts is 2 + 0 + 1 = 3 meters.

Difficulty: competition

Starter code:

Solutions:
import itertools

unfold = itertools.chain.from_iterable

speedup = 400000

def jumps(a):
    d = speedup
    while d < a - 1:
        c = (a + d - 1) // d
        d = (a + c - 2) // (c - 1)
        yield d


def calc(d):
    return sum(d - 1 - (i - 1) % d for i in a)

def ans():
    for d, pd in zip(D, D[1:]):
        d -= 1
        cd = calc(d)
        if cd <= k:
            return d
        if d == pd:
            continue
        cpd = calc(pd)
        if d - pd >= (cd - k) * (d - pd) / (cd - cpd):
            return d - (cd - k) * (d - pd) / (cd - cpd)
    return 1

n, k = map(int, input().split())
a = list(map(int, input().split()))
speedup = min(speedup, 2 * int(max(a) ** 0.5))

D = sorted(set(range(1, speedup + 1)).union([max(a) + k + 1]).union(set(
    unfold(map(jumps, a)))), reverse=True)
    
print('%d' % ans())

import itertools

unfold = itertools.chain.from_iterable

def jumps(a):
    d = speedup
    while d < a - 1:
        c = (a + d - 1) // d
        d = (a + c - 2) // (c - 1)
        yield d


def calc(d):
    return sum(d - 1 - (i - 1) % d for i in a)

def ans():
    for d, pd in zip(D, D[1:]):
        d -= 1
        cd = calc(d)
        if cd <= k:
            return d
        if d == pd:
            continue
        cpd = calc(pd)
        if d - pd >= (cd - k) * (d - pd) / (cd - cpd):
            return d - (cd - k) * (d - pd) / (cd - cpd)
    return 1

n, k = map(int, input().split())
a = list(map(int, input().split()))
speedup = int(max(a) ** 0.5)

D = sorted(set(range(1, speedup + 1)).union([max(a) + k + 1]).union(set(
    unfold(map(jumps, a)))), reverse=True)
    
print('%d' % ans())

import itertools
import time

unfold = itertools.chain.from_iterable

t = time.time() + 1900
def jumps(a):
    d = speedup
    if time.time() > t:
        print(anss)
        return
    try:
        while True:
            c = (a + d - 1) // d
            d = (a + c - 2) // (c - 1)
            yield d
    except:
        return

#    while d < a - 1:
#        c = (a + d - 1) // d
#        d = (a + c - 2) // (c - 1)
#        yield d

def calc(d):
    return (d - 1) * len(a) - sum(i % d for i in a)

def ans1(D):
    for d in D:
        d -= 1
        if calc(d) <= k:
            return d
    return 1

def ans():
    for d, pd in zip(D, D[1:]):
        if time.time() > t:
            return anss
        d -= 1
        cd = calc(d)
        if cd <= k:
            return d
        if d == pd:
            continue
        cpd = calc(pd)
        if (d - pd) * (cd - cpd) >= ((cd - k) * (d - pd) + cd - cpd - 1):
            return d - ((cd - k) * (d - pd) + cd - cpd - 1) // (cd - cpd)
    return anss

n, k = map(int, input().split())
a = list(map(int, input().split()))
speedup = int(2 * max(a) ** 0.55)

lb = int(max(a) ** 0.1 + 10)

a = [i - 1 for i in a]
anss = ans1(sorted(range(2, lb + 1), reverse=True))
if anss <= lb / 2:
    print(anss)
    return

a = [i + 1 for i in a]
D = sorted(set(range(lb + 1, speedup + 1)).union(set([speedup, max(a) + k + 1]).union(set(
    unfold(map(jumps, a))))), reverse=True)

a = [i - 1 for i in a]
print(int(ans()))