#CW17. 消除序列(sequence)

消除序列(sequence)

题目描述

进行一个如下的消除序列游戏。

第 00 秒时,你有一个能力值 x=0x=0 以及一个整数 y=1y=1。还有一个长度为 nn 的序列 aia_i。

游戏一共会进行 mm 秒。对于每个不大于 mm 的正整数 ii:

  • 在第 ii 秒开始时,能力值会增大 yy。即 x←x+yx \leftarrow x+y。
  • 在第 ii 秒结束时,你可以进行任意次操作(可以为 00 次)。
  • 每次操作,你需要选择一个未被消除的 jj 满足 aj≤xa_j \le x,接着消耗 aja_j 的能力值并消除序列的第 jj 项,在此之后整数 yy 会增加 11。即 x←x−ajx \leftarrow x-a_j,y←y+1y \leftarrow y+1。

你的目标是,在游戏结束后,最大化能力值。即最大化 xx。

输入格式

第一行包含两个正整数 n,mn, m。

第二行包含 nn 个正整数 aia_i。

输出格式

输出一行,包含一个整数,表示在游戏结束后能达到的最大的能力值。

样例 1 输入

3 6
1 1 3

样例 1 输出

13

样例 2 输入

3 5
1 1 1

样例 2 输出

12

数据范围

对于所有测试数据,保证:1≤n≤5×1051 \le n \le 5 \times 10^5,1≤m≤1091 \le m \le 10^9,1≤ai≤1091 \le a_i \le 10^9。

测试点 n≤n \le m≤m \le
1∼51 \sim 5 55
6∼106 \sim 10 10001000
11∼1511 \sim 15 5×1055 \times 10^5 10510^5
16∼2016 \sim 20 10910^9