U23344.采蘑菇的小白狼

普及-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

​ 身为白白草原狼群首领的儿子,小白狼从一出生就被教会了不许挑食的好习惯,于是不管是素的还是荤的小白狼都照吃不误。

​ 现在,狼群又一次大获丰收,大白狼很高兴,决定做一顿蘑菇炖小鸡吃吃,于是就派小白狼出去采蘑菇,小白狼一听到有地方需要自己,高兴的决定出门把附近的蘑菇都采光,但是却被大白狼敲了个脑袋瓜。大白狼希望小白狼能够给其他动物留下蘑菇,我们自己只取我们需要的就好了。于是乎,小白狼就顶着大包出门采蘑菇去了。

​ 大白狼在小白狼出行前告诉他炖汤需要 mm 个蘑菇,希望小白狼采集 m\le m 的蘑菇,同时小白狼一共可以前往森林的 nn 个地方,每到第 ii 地方就会采集 cic_i 个蘑菇,而小白狼可以选择任意一个地点出发,从这个地点或之后的任意地点出来,所经过地点的编号是连续的,并且小白狼只能选取一次,经过的地方的蘑菇都会被它采走。
比如:

一共有6个地方可以去,
小白狼可以选择从2号点进去,3号点出来;
也可以选择1号点进去,6号点出来.

请问小白狼最后能带回多少蘑菇?

输入格式

第一行,分别输入两个正整数 n,m.n,m.
随后nn行,每行输入一个正整数 cic_i 代表第 ii 号森林所拥有的蘑菇数量。

输出格式

一个正整数,代表小白狼最后带出蘑菇的总数。

输入输出样例

  • 输入#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%的数据,1n105,106<m<1012,1ci<1091\le n \le 10^5,10^6< m < 10^{12},1\le c_i<10^9.

样例一:小白狼刚好可以把所有蘑菇全拿走,即从1号进去,10号出来.
样例二:小白狼可以从3号进去,5号出来,一共采12个蘑菇.

首页