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----- 2 3 8 20

-----Sample Output----- 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.