简单版本和困难版本之间的唯一区别是限制。
波利卡普必须写一份课程作业。课程作业由 $$$m$$$ 页组成。
Polycarp 还有 $$$n$$$ 杯咖啡。第 $$$i$$$ 杯 Polycarp 中的咖啡含有 $$$a_i$$$ 咖啡因。波利卡普可以喝几杯咖啡(每杯不超过一次)。他可以按任何顺序喝杯子。波利卡普立即并完全喝完每一杯(即他不能将任何一杯分成几天)。
当然,课程作业不是一天之内写成的(至少在 Berland 的完美世界中是这样)。
让我们考虑一下坡旅甲的某一天的工作。考虑 Polycarp 在这一天喝 $$$k$$$ 杯咖啡,Polycarp 在这一天喝的咖啡因剂量为 $$$a_{i_1}, a_{i_2}, \dots, a_{i_k}$$$。然后他喝的第一杯给他能量写$$$a_{i_1}$$$页课程作业,第二杯给他能量写$$$max(0, a_{i_2} - 1)$$$页,第三杯给他能量写$$$max(0, a_{i_3} - 2)$$$页,...,第$$$k$$$页给他能量写$$$max(0, a_{i_k} - k + 1)$$$ 页。
如果波利卡普某天不喝咖啡,他那天就根本无法写作业。
波利卡普必须尽快完成他的课程作业(花费最少的天数来完成)。你的任务是找出这个天数或者说这是不可能的。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — 咖啡的杯数和课程作业的页数。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 杯中咖啡的咖啡因剂量。
输出
如果无法写出课程作业,请打印 -1。否则打印 Polycarp 需要完成该任务的最少天数。
示例
输入 #1
5 8 2 3 1 1 2
输出 #1
4
输入 #2
7 10 1 3 4 2 1 4 2
输出 #2
2
输入 #3
5 15 5 5 5 5 5
输出 #3
1
输入#4
5 16 5 5 5 5 5
输出#4
2
输入 #5
5 26 5 5 5 5 5
输出 #5
-1
注意
在第一个示例中,Polycarp 可以在第一天喝第四杯(并写 $$$1$$$ 页),在第二天喝第一杯和第二杯(并写 $$$2 + (3 - 1) = 4$$$ 页),在第三天喝第五杯(并写 $$$2$$$ 页),在第四天喝第三杯(并写 $$$1$$$ 页),所以答案是$$$4$$$。显然三天以内是不可能写完作业的。
在第二个示例中,Polycarp 在第一天可以喝第三杯、第四杯和第二杯(并写下 $$$4 + (2 - 1) + (3 - 2) = 6$$$ 页),并在第二天喝第六杯(并写下 $$$4$$$ 页),因此答案为 $$$2$$$。很明显,波利卡普不可能在这次考试中一天内写完全部课程作业。
在第三个示例中,Polycarp 可以在第一天喝完所有杯咖啡,并写出 $$$5 + (5 - 1) + (5 - 2) + (5 - 3) + (5 - 4) = 15$$$ 页的课程作业。
在第四个示例中,波利卡普不能在第一天喝完所有杯子,而应该在第二天喝掉其中一杯。因此,第一天他将写 $$$5 + (5 - 1) + (5 - 2) + (5 - 3) = 14$$$ 页的课程作业,第二天他将写 $$$5$$$ 页的课程作业。这足以完成它。
在第五个示例中,Polycarp 根本无法写出整个课程作业,即使他每天会喝一杯咖啡,所以答案是 -1。