CF1469F.Power Sockets

// We decided to drop the legend about the power sockets but feel free to come up with your own :^)

Define a chain:

• a chain of length $1$ is a single vertex;
• a chain of length $x$ is a chain of length $x-1$ with a new vertex connected to the end of it with a single edge.

You are given $n$ chains of lengths $l_1, l_2, \dots, l_n$. You plan to build a tree using some of them.

• Each vertex of the tree is either white or black.
• The tree initially only has a white root vertex.
• All chains initially consist only of white vertices.
• You can take one of the chains and connect any of its vertices to any white vertex of the tree with an edge. The chain becomes part of the tree. Both endpoints of this edge become black.
• Each chain can be used no more than once.
• Some chains can be left unused.

The distance between two vertices of the tree is the number of edges on the shortest path between them.

If there is at least $k$ white vertices in the resulting tree, then the value of the tree is the distance between the root and the $k$-th closest white vertex.

What's the minimum value of the tree you can obtain? If there is no way to build a tree with at least $k$ white vertices, then print -1.

// 我们决定删去关于电源插座的背景故事，但欢迎你自行构思一个 :^)

定义一条“链”如下：

• 长度为 $1$ 的链是一个单独的顶点；
• 长度为 $x$ 的链，是由一条长度为 $x-1$ 的链在其末端添加一个新顶点，并用一条边连接而成。

你被给定 $n$ 条链，其长度分别为 $l_1, l_2, \dots, l_n$。你计划用其中一部分链来构造一棵树。

• 树中的每个顶点要么是白色，要么是黑色；
• 树初始时仅包含一个白色的根顶点；
• 所有链初始时均由白色顶点组成；
• 你可以选取其中一条链，并将该链的任意一个顶点通过一条边连接到当前树中任意一个白色顶点上；该链由此成为树的一部分；这条边的两个端点均变为黑色；
• 每条链最多只能使用一次；
• 部分链可以不使用。

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

若最终得到的树中至少含有 $k$ 个白色顶点，则该树的“值”定义为：根顶点与第 $k$ 个最近的白色顶点之间的距离（按距离从小到大排序，第 $k$ 个即为距离第 $k$ 小的白色顶点）。

你能获得的树的最小可能值是多少？若无法构造出至少含 $k$ 个白色顶点的树，则输出 -1。

The first line contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$, $2 \le k \le 10^9$) — the number of chains and the minimum number of white vertices a tree should have to have a value.

The second line contains $n$ integers $l_1, l_2, \dots, l_n$ ($3 \le l_i \le 2 \cdot 10^5$) — the lengths of the chains.

第一行包含两个整数 $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$）—— 表示各条链的长度。

Print a single integer. If there is no way to build a tree with at least $k$ white vertices, then print -1. Otherwise, print the minimum value the tree can have.

输出一个整数。如果无法构建一棵至少包含 $k$ 个白色顶点的树，则输出 $-1$；否则，输出该树可能的最小值。

You are allowed to not use all the chains, so it's optimal to only use chain of length $4$ in the second example.

允许不使用全部链条，因此在第二个例子中，仅使用长度为 $4$ 的链条是最优的。