4218 - 魔法药水(potion)

题目描述

作为 G 国的国家炼金术师,你有着超高的魔法造诣。

现在在你的面前有 n 种材料,材料 i 的魔力为 a_i

你想从这些材料中选择出一种或几种混合在一起制作一种药水。你知道不同的材料混合会给药水带来持续魔力增加效果,当你混合 k 种材料时,药水每单位时间的魔力值会增加 k。此外,材料本身的魔力值之和为药水的初始魔力值。

你在一开始(即 0 时刻)就会把所有材料混合好

输入

输入第一行包含两个数字 n,m,分别表示材料数量,目标药水魔力值。

输入第二行包含 n 个整数 a_i,表示第 i 种材料的魔力值。

输出

输出共一行,表示你能获得魔力正好为 m 的药水的最早时间。

样例

输入

3 9999999999
3 6 8

输出

4999999994

输入

1 1000000000000000000
1

输出

999999999999999999
说明

样例 1 解释

材料 1 和材料 3混合制成的药水在 0 时的魔力为 3 + 8 = 11,每秒增加 2 魔力值,因此在 4999999994 时刻的魔力为 11 + 2 \times 4999999994 = 9999999999,也就是最早可能的时间。

数据规模与约定

  • 对于 20\% 的数据,保证 n \le 2
  • 对于 50\% 的数据,保证 n \le 20
  • 对于 70\% 的数据,保证 n \le 50
  • 对于 100\% 的数据,保证 1 \le n \le 100, 1 \le a_i \le 1 \times 10^7,1 \times 10^9 \le m \le 1 \times 10^{18}
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题