HZNUOJ

剪剪剪

Tags:     二分答案
Time Limit:  1 s      Memory Limit:   32 MB
Submission:450     AC:85     Score:94.95

Description

喜爱剪东西的Muin喜欢剪纸。这是一个对Muin来说很开心的事情,但是她的剪刀比较奇葩且她的爱好比较独特,她的剪刀不会完全的去剪一张纸。她的剪刀可以设置一个长度参数H(cm),例如,如果一叠纸的长度分别为20,15,10和17,Muin把剪刀设置到15cm的长度,裁剪后纸片剩下的长度将是15,15,10和15,Muin共得到7cm长度的纸。Muin又为了有趣,不愿意浪费纸张,所以她希望找到剪刀的最大的整数长度H,使得她能得到纸张至少为Mcm。换句话说,如果H再升高1cm,她将得不到Mcm纸。

但是Muin又比较逗,自己算不出来,所以希望你帮助她找到这个H。

Input

测试数据有多组,对于每组测试数据:

第1行:2个整数N和M,N表示纸片的数量(1<=N<=100000),M表示需要的纸张总长度(1<=M<=200000000)

第2行:N个整数表示每张纸的长度,值均不超过200000000。数据保证所有纸张长度之和大于M,因此必有解。

Output

对于每组测试数据,输出对应的H并换行。

Samples

input
5 20 4 42 40 26 46
output
36

Author

YU, Dongwei

Source

2014杭师计算机协会第一届程序设计竞赛