are given n chains of lengths l1,l2,… ,ln. You intend to fabricate a tree utilizing some of them. Every vertex of the tree is either white or dark. The tree at first just has a white root vertex.
Correct answer will be upvoted else Multiple Downvoted. Computer science.
You are given n chains of lengths l1,l2,… ,ln. You intend to fabricate a tree utilizing some of them.
Every vertex of the tree is either white or dark.
The tree at first just has a white root vertex.
All chains at first comprise just of white vertices.
You can take one of the chains and interface any of its vertices to any white vertex of the tree with an edge. The chain turns out to be important for the tree. The two endpoints of this edge become dark.
Each chain can be utilized close to once.
A few chains can be left unused.
The distance between two vertices of the tree is the number of edges on the most brief way between them.
Assuming there is essentially k white vertices in the subsequent tree, the worth of the tree is the distance between the root and the k-th nearest white vertex.
What's the base worth of the tree you can get? In case it is absolutely impossible to construct a tree with basically k white vertices, then, at that point, print - 1.
Input
The principal line contains two integers n and k (1≤n≤2⋅105, 2≤k≤109) — the number of chains and the base number of white vertices a tree ought to must have a worth.
The subsequent line contains n integers l1,l2,… ,ln (3≤li≤2⋅105) — the lengths of the chains.
Output
Print a solitary integer. In case it is absolutely impossible to construct a tree with essentially k white vertices, then, at that point, print - 1. In any case, print the base worth the tree can have
Step by step
Solved in 4 steps with 1 images
