← 返回题目列表

Codeforces · 1118/D1

D1. 咖啡和课程作业(简单版)

中文机器翻译题面 查看原题

简单版本和困难版本之间的唯一区别是限制。

波利卡普必须写一份课程作业。课程作业由 $$$m$$$ 页组成。

Polycarp 还有 $$$n$$$ 杯咖啡。第 $$$i$$$ 杯中的咖啡含有 $$$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 100$$$, $$$1 \le m \le 10^4$$$) — 咖啡的杯数和课程作业的页数。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$),其中 $$$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$$$ 页的课程作业。

在第四个示例中,Polycarp 不能在第一天喝完所有杯子,而应该在第二天喝其中一杯。因此,第一天他将写 $$$5 + (5 - 1) + (5 - 2) + (5 - 3) = 14$$$ 页的课程作业,第二天他将写 $$$5$$$ 页的课程作业。这足以完成它。

在第五个示例中,Polycarp 根本无法写出整个课程作业,即使他每天会喝一杯咖啡,所以答案是 -1。