问题 AY: 欢聚一堂

$N$个小朋友欢聚一堂，第$i$个小朋友有A i A_iAi个糖果

一次糖果赠送事件的定义是：小朋友$i$赠送给小朋友$j$一颗糖（A i A_iAi减1，A j A_jAj加1）

特殊的是，小朋友的糖果数量可以为负。(如果小朋友$i$已经没有糖果了，但他对小朋友$j$进行一次糖果赠送事件，那么事件完成之后，小朋友$i$具有$-1$颗糖果)

最多进行$K$次糖果赠送事件的前提下，请你找到最大的一个整数$a$，使得$a$是所有小朋友糖果的整数倍。

输入包括$2$行
第一行空格隔开的两个正整数$N$和$K$，代表共有$N$个小朋友，最多进行$K$次糖果赠送事件
第二行空格隔开的$N$个正整数A i A_iAi，代表$N$个小朋友的初始糖果数量。

数据范围

• $2\le N\le 500$
• 1 ≤ A i ≤ 1 0 6 1leq A_ileq 10^61≤Ai≤106
• 0 ≤ K ≤ 1 0 9 0leq K leq 10^90≤K≤109

输出一行一个整数$a$，使得$a$是进行不多于$K$次的交换事件后，每个小朋友的糖果数量都是a的整数倍。
在所有符合条件的$a$中，输出最大的那一个。

例如有$2$个小朋友，最多进行$10$次糖果交换事件，初始时两个小朋友具有的糖果数量分别是$3$和$5$。
那么可以进行$3$次糖果交换($3<10$)，之后小朋友分别具有$0$和$8$颗糖果。
此时有$a=8$，满足$0=0\times 8$、$8=1\times 8$，因此$8$是符合条件的$a$。
找不到一种不多于$10$次的交换方法，使得交换之后有符号条件的更大的$a$。

2 10
3 5

8

题解点我