← 返回题目列表

Codeforces · 1469/F

F. 电源插座

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

// 我们决定放弃有关电源插座的图例,但请随意提出您自己的:^)

定义一条链:

- 长度为 $$$1$$$ 的链是单个顶点;
- 长度为 $$$x$$$ 的链是长度为 $$$x-1$$$ 的链,其中一个新顶点通过一条边连接到其末端。

给你 $$$n$$$ 长度的链 $$$l_1, l_2, \dots, l_n$$$。您计划使用其中的一些来构建一棵树。

- 树的每个顶点都是白色或黑色。
- 树最初只有一个白色的根顶点。
- 所有链最初仅由白色顶点组成。
- 您可以选取其中一条链并将其任何顶点连接到带有边的树的任何白色顶点。链条成为树的一部分。该边缘的两个端点都变成黑色。
- 每条链只能使用一次。
- 一些链可以不使用。

树的两个顶点之间的距离是它们之间的最短路径上的边数。

如果生成的树中至少有 $$$k$$$ 个白色顶点,则树的值是根与第 $$$k$$$ 个最近的白色顶点之间的距离。

您可以获得的树的最小值是多少?如果无法构建至少具有 $$$k$$$ 白色顶点的树,则打印 -1。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$2 \le k \le 10^9$$$) - 树的链数和白色顶点的最小数量应该有一个值。

第二行包含 $$$n$$$ 整数 $$$l_1, l_2, \dots, l_n$$$ ($$$3 \le l_i \le 2 \cdot 10^5$$$) — 链的长度。

输出

打印单个整数。如果无法构建至少具有 $$$k$$$ 白色顶点的树,则打印 -1。否则,打印树可以具有的最小值。

示例

输入 #1

1 2
3

输出 #1

2

输入 #2

3 3
4 3 3

输出 #2

3

输入 #3

3 5
4 3 4

输出 #3

4

输入#4

2 10
5 7

输出#4

-1

注意

您可以不使用所有链,因此最好在第二个示例中仅使用长度为 $$$4$$$ 的链。