问题 E: 剪彩带

问题 E: 剪彩带

时间限制: 1 Sec  内存限制: 128 MB
提交: 263  解决: 87
[状态] [讨论版] [提交] [命题人:]
题目描述

小明和自己的一群伙伴去帮助老师剪裁彩带。

每个人发到手中的彩带的长度都不是完全相同的,每次小明会说,裁到x的位置,那么每个人都会从自己彩带1位置往后找到x的地方剪下然后上交给小明(即彩带x+1到 彩带末尾的这一段)。如果不够长小命就会接着再说出一个x大家照做。

其实小明只是想一共裁出总和至少长为m的彩带,但是每次比较太慢了,现在小明相向你请教,请你告诉小明让所有人从x处裁减就能获得长至少为m的彩带,并且保证x最大,也就是从x+1处的话就不够了。


输入



第一行两个整数n(1 <= n <= 106)和m(1 <= m <= 106),n代表裁剪彩带及裁剪人的个数,m代表彩带的总需求长度。

第二行n个整数代表每条彩带的长度(1 <= 彩带长度 <= 109)。



输出

输出一个整数代表最大的x的值

样例输入 Copy
4 7
20 15 10 17
样例输出 Copy
15