Problem2941--投票箱

2941: 投票箱

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

今天,科丁王国举行总统大选,18岁或以上的每一位居民都被要求投票,政府有许多投票箱,不幸的是,负责城市间运送投票箱的工人几个月前被解雇了。
因此,政府无法将投票箱灵活运送到每个城市、让选民投票;你的任务是计算一个有效的投票箱分配过程,使得:
1)每个城市至少分配一个投票箱,政府会平均安排选民到自己城市的投票箱中投票
2)投票箱能接纳的最大选民数量最小化

Input

每个测试用例的第一行包含整数N(1<=N<=500000)表示城市数量、B(N<=B<=2000000)表示投票箱数量。
以下N行中的每一行包含一个整数Ai(1<=Ai<=5000000),表示第i个城市的人口。
每种每个用例结束后都有一个空白行。输入的最后一行将包含-1 -1,不应进行处理。


用例解析如下:
1)第一个测试用例中,两个投票箱分别指向第一个城市和第二个城市,并且在有效的分配下、投票箱中的最大选民数至少有10万人。
2)第二个测试用例中,分别将1、2、2、1个投票箱分配给4个城市,那么:
-第一个城市的1个投票箱有120人投票
-第二个城市的2个投票箱有1340人投票
-第三个城市的2个投票箱有1700人投票
-第四个城市的1个投票箱有200人投票
这种情况下,投票箱中的最大选民数至少有1700人

Output

对于每个用例,程序输出一个整数,即在最有效分配的情况下,投票箱中的最大选民数至少有多少?

Sample Input Copy

2 7
200000
500000

4 6
120
2680
3400
200

-1 -1

Sample Output Copy

100000
1700

Source/Category