U23344.采蘑菇的小白狼
普及-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
身为白白草原狼群首领的儿子,小白狼从一出生就被教会了不许挑食的好习惯,于是不管是素的还是荤的小白狼都照吃不误。
现在,狼群又一次大获丰收,大白狼很高兴,决定做一顿蘑菇炖小鸡吃吃,于是就派小白狼出去采蘑菇,小白狼一听到有地方需要自己,高兴的决定出门把附近的蘑菇都采光,但是却被大白狼敲了个脑袋瓜。大白狼希望小白狼能够给其他动物留下蘑菇,我们自己只取我们需要的就好了。于是乎,小白狼就顶着大包出门采蘑菇去了。
大白狼在小白狼出行前告诉他炖汤需要 m 个蘑菇,希望小白狼采集 ≤m 的蘑菇,同时小白狼一共可以前往森林的 n 个地方,每到第 i 地方就会采集 ci 个蘑菇,而小白狼可以选择任意一个地点出发,从这个地点或之后的任意地点出来,所经过地点的编号是连续的,并且小白狼只能选取一次,经过的地方的蘑菇都会被它采走。
比如:
一共有6个地方可以去,
小白狼可以选择从2号点进去,3号点出来;
也可以选择1号点进去,6号点出来.
请问小白狼最后能带回多少蘑菇?
输入格式
第一行,分别输入两个正整数 n,m.
随后n行,每行输入一个正整数 ci 代表第 i 号森林所拥有的蘑菇数量。
输出格式
一个正整数,代表小白狼最后带出蘑菇的总数。
输入输出样例
输入#1
10 55 1 2 3 4 5 6 7 8 9 10
输出#1
55
输入#2
5 13 1 2 3 4 5
输出#2
12
说明/提示
对于100%的数据,1≤n≤105,106<m<1012,1≤ci<109.
样例一:小白狼刚好可以把所有蘑菇全拿走,即从1号进去,10号出来.
样例二:小白狼可以从3号进去,5号出来,一共采12个蘑菇.