题目描述
进行一个如下的消除序列游戏。
第 0 秒时,你有一个能力值 x=0 以及一个整数 y=1。还有一个长度为 n 的序列 ai。
游戏一共会进行 m 秒。对于每个不大于 m 的正整数 i:
- 在第 i 秒开始时,能力值会增大 y。即 x←x+y。
- 在第 i 秒结束时,你可以进行任意次操作(可以为 0 次)。
- 每次操作,你需要选择一个未被消除的 j 满足 aj≤x,接着消耗 aj 的能力值并消除序列的第 j 项,在此之后整数 y 会增加 1。即 x←x−aj,y←y+1。
你的目标是,在游戏结束后,最大化能力值。即最大化 x。
输入格式
第一行包含两个正整数 n,m。
第二行包含 n 个正整数 ai。
输出格式
输出一行,包含一个整数,表示在游戏结束后能达到的最大的能力值。
样例 1 输入
3 6
1 1 3
样例 1 输出
13
样例 2 输入
3 5
1 1 1
样例 2 输出
12
数据范围
对于所有测试数据,保证:1≤n≤5×105,1≤m≤109,1≤ai≤109。
| 测试点 |
n≤ |
m≤ |
| 1∼5 |
5 |
| 6∼10 |
1000 |
| 11∼15 |
5×105 |
105 |
| 16∼20 |
109 |