#include <iostream>
#include <fstream>
#include <vector>
#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>

#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

typedef long long ll;
typedef long double ld;

using namespace std;

const int MAXN = 2E5 + 1;
const int INF = 1E9 + 1;

ll n, k, a[MAXN], R;

// дерево отрезков
// t[i] хранит сумму cnt[j], j:[0, i]
ll t[4 * MAXN];

// дерево отрезков
// p[i] хранит LAZY-добавляемое значение.
ll p[4 * MAXN];

// функция проталкивания значения снизу вверх
void push(int v, int l, int r)
{
	// проталкиваем вниз значение p[v]
	p[v * 2] += p[v];
	p[v * 2 + 1] += p[v];

	t[v] += p[v] * (r - l + 1);
	// а само значение обнуляем
	p[v] = 0;
}

void update(int v, int l, int r, int lq, int rq, int value)
{
	push(v, l, r);
	if (lq > rq)
		return;

	if (l == lq && r == rq)
	{
		p[v] += value;
		push(v, l, r);
		return;
	}

	int m = (l + r) / 2;
	update(v * 2, l, m, lq, min(rq, m), value);
	update(v * 2 + 1, m + 1, r, max(lq, m + 1), rq, value);
	t[v] = t[v * 2] + t[v * 2 + 1];
}

int get(int v, int l, int r, int lq, int rq)
{
	push(v, l, r);
	if (lq > rq)
		return 0;

	if (l == lq && r == rq)
	{
		return t[v];
	}

	int m = (l + r) / 2;
	ll res = get(v * 2, l, m, lq, min(rq, m)) + get(v * 2 + 1, m + 1, r, max(lq, m + 1), rq);
	t[v] = t[v * 2] + t[v * 2 + 1];
	return res;
}

ll search(int v, int l, int r, int cnt)
{
	push(v, l, r);

	if (l == r)
	{
		return l;
	}

	// ищем минимальную правую границу (индекс it), для которого get(0, it) >= k
	ll b = INF;
	int m = (l + r) / 2;

	push(v * 2, l, m);
	push(v * 2 + 1, m + 1, r);

	if (t[2 * v] >= cnt)
	{
		b = search(2 * v, l, m, cnt);
	}
	else if (t[2 * v + 1] >= cnt - t[2 * v])
	{
		b = search(2 * v + 1, m + 1, r, cnt - t[2 * v]);
	}

	t[v] = t[v * 2] + t[v * 2 + 1];

	return b;
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	// cout.setf(ios::fixed);
	// cout.precision(6);

	// ifstream in("4.txt");
	// cin.rdbuf(in.rdbuf());

	cin >> n >> k;

	// Можно придумать жадный алгоритм решения этой задачи:

	// 1. Можно заметить, что если уж мы присоединяем цепь, то мы должны всегда подцеплять ее примерно "за середину"
	// Таким образом мы всегда делаем дерево наименьшей высоты. А нам именно это и надо.

	// 2. Нужно всегда стараться брать сначала самые длинные цепи. Действительно, чем длиннее цепь, тем раньше мы закончим процесс построения дерева
	// т.к мы раньше получим требуемое значение "белых вершин" (k)

	// 3. Всегда нужно  цеплять очередную цепочку за самую ближайшую к корню "белую вершину"

	// С первыми двумя увтверждениями все ясно. А вот третье требует докаательства.

	// Пусть Оптимальный ответ на задачу равен D. мы же строим дерево "по-нашему" алгоритму. Пусть нам требуется получить в дереве не менее X
	// белых вершин. Рассмотрим процесс подвешивания очепрдной цепи. Возможны два варианта:

	// a) Мы добавляем цепь, но пока не достикаем требуемого количества белых вершин X
	// б) После добавления цепочки мы достигли отметки в X вершин.

	// Если имеем вариант а) то просто продолжаем процесс, пока не получим вариант б)
	// Рассмотрим вариант б). Пусть мы подцепили очередную цепь на уровень d дерева.
	// Если бы d > D, то это означает, что на каком-то шаге мы подцепили очередную цепь "не вплотную" к самой ближайшей к корню белой вершине.
	// Но этого быть не может по построению нашего дерева. Поэтому d <= D.

	// Предположим, что d == D. Но и этого не может быть, т.к наш алгоритм работает так, чт оон ВСЕГДА выбираем самую длинную цепь и подцепляет ее
	// а нам пришлось подсоединить еще одну цепь на цровень d, чтобы довести значение белых вершин до X.

	// предположим, что D == d + 1.
	// Этого тоже не может быть практически по тем же соображений что и в предыдущем пункте. Т.к мы подцепили звено на уровне d, то увеличить
	// количество белых вершин мы сможем только на уровне d + 2.

	// т.е. D >= d + 2, но это означает, что на любом шаге нашего алгоритма у нас результат не хуже чем у оптимального (у нас тоже уровень находится
	// не ниже чем на d + 2, но за счет того, что у нас всегда уменьшается количсетво звеньев мы точно не уступаем оптимальному алгоритму.

	// пусть cnt[i] - количество белых вершин на уровне i
	// Стоит задача найти наименьшее i=it такое, что SUM(cnt[i], i <= it) >= k
	// Таким образом, алгоритм решения такой:

	// Сортируем все звенья в DESC порядке по длине
	// Берем максимальный и вешаем на дерево
	// Обновляем cnt[i], для всех i, что лежат ниже точки присоединения нового звена (это можно сделать за LogN с помощью дерева отрезков)
	// Проверяем, можем ли мы найти такое it, что SUM(cnt[i], i <= it) >= k (тоже за LOGN)

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	sort(a, a + n);
	int level = 0;
	R = INF;

	int n2 = a[n - 1] + 500;

	// нужно добавить корневую вершину на 0-ой уровен.
	update(1, 0, n2, 0, 0, 1);

	for (int i = n - 1; i >= 0; i--)
	{
		// т.к мы всегда прикрепляем звенья как можно выше, то смотрим, если на уровне level у нас не осталось больше белых вершин,
		// то переходим на уровень ниже
		while (get(1, 0, n2, 0, level) == 0)
			level++;

		// убираем одну вершину с уровня level
		update(1, 0, n2, level, level, -1);

		// т.к каждая цепь разбивается "примерно пополам", то добавляем обе части:
		update(1, 0, n2, level + 2, level + 2 + (a[i] - 1) / 2 - 1, 1);
		update(1, 0, n2, level + 2, level + 2 + a[i] / 2 - 1, 1);

		R = min(R, search(1, 0, n2, k));
	}

	if (R == INF)
		R = -1;

	cout << R << endl;

	return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

// 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, ..., 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.

Input

The first line contains two integers n and k (1 ≤ n ≤ 2 ⋅ 10^5, 2 ≤ k ≤ 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, ..., l_n (3 ≤ l_i ≤ 2 ⋅ 10^5) — the lengths of the chains.

Output

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.

Examples

Input


1 2
3


Output


2


Input


3 3
4 3 3


Output


3


Input


3 5
4 3 4


Output


4


Input


2 10
5 7


Output


-1

Note

<image>

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

### Response

```cpp
#include <iostream>
#include <fstream>
#include <vector>
#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>

#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

typedef long long ll;
typedef long double ld;

using namespace std;

const int MAXN = 2E5 + 1;
const int INF = 1E9 + 1;

ll n, k, a[MAXN], R;

// дерево отрезков
// t[i] хранит сумму cnt[j], j:[0, i]
ll t[4 * MAXN];

// дерево отрезков
// p[i] хранит LAZY-добавляемое значение.
ll p[4 * MAXN];

// функция проталкивания значения снизу вверх
void push(int v, int l, int r)
{
	// проталкиваем вниз значение p[v]
	p[v * 2] += p[v];
	p[v * 2 + 1] += p[v];

	t[v] += p[v] * (r - l + 1);
	// а само значение обнуляем
	p[v] = 0;
}

void update(int v, int l, int r, int lq, int rq, int value)
{
	push(v, l, r);
	if (lq > rq)
		return;

	if (l == lq && r == rq)
	{
		p[v] += value;
		push(v, l, r);
		return;
	}

	int m = (l + r) / 2;
	update(v * 2, l, m, lq, min(rq, m), value);
	update(v * 2 + 1, m + 1, r, max(lq, m + 1), rq, value);
	t[v] = t[v * 2] + t[v * 2 + 1];
}

int get(int v, int l, int r, int lq, int rq)
{
	push(v, l, r);
	if (lq > rq)
		return 0;

	if (l == lq && r == rq)
	{
		return t[v];
	}

	int m = (l + r) / 2;
	ll res = get(v * 2, l, m, lq, min(rq, m)) + get(v * 2 + 1, m + 1, r, max(lq, m + 1), rq);
	t[v] = t[v * 2] + t[v * 2 + 1];
	return res;
}

ll search(int v, int l, int r, int cnt)
{
	push(v, l, r);

	if (l == r)
	{
		return l;
	}

	// ищем минимальную правую границу (индекс it), для которого get(0, it) >= k
	ll b = INF;
	int m = (l + r) / 2;

	push(v * 2, l, m);
	push(v * 2 + 1, m + 1, r);

	if (t[2 * v] >= cnt)
	{
		b = search(2 * v, l, m, cnt);
	}
	else if (t[2 * v + 1] >= cnt - t[2 * v])
	{
		b = search(2 * v + 1, m + 1, r, cnt - t[2 * v]);
	}

	t[v] = t[v * 2] + t[v * 2 + 1];

	return b;
}

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	// cout.setf(ios::fixed);
	// cout.precision(6);

	// ifstream in("4.txt");
	// cin.rdbuf(in.rdbuf());

	cin >> n >> k;

	// Можно придумать жадный алгоритм решения этой задачи:

	// 1. Можно заметить, что если уж мы присоединяем цепь, то мы должны всегда подцеплять ее примерно "за середину"
	// Таким образом мы всегда делаем дерево наименьшей высоты. А нам именно это и надо.

	// 2. Нужно всегда стараться брать сначала самые длинные цепи. Действительно, чем длиннее цепь, тем раньше мы закончим процесс построения дерева
	// т.к мы раньше получим требуемое значение "белых вершин" (k)

	// 3. Всегда нужно  цеплять очередную цепочку за самую ближайшую к корню "белую вершину"

	// С первыми двумя увтверждениями все ясно. А вот третье требует докаательства.

	// Пусть Оптимальный ответ на задачу равен D. мы же строим дерево "по-нашему" алгоритму. Пусть нам требуется получить в дереве не менее X
	// белых вершин. Рассмотрим процесс подвешивания очепрдной цепи. Возможны два варианта:

	// a) Мы добавляем цепь, но пока не достикаем требуемого количества белых вершин X
	// б) После добавления цепочки мы достигли отметки в X вершин.

	// Если имеем вариант а) то просто продолжаем процесс, пока не получим вариант б)
	// Рассмотрим вариант б). Пусть мы подцепили очередную цепь на уровень d дерева.
	// Если бы d > D, то это означает, что на каком-то шаге мы подцепили очередную цепь "не вплотную" к самой ближайшей к корню белой вершине.
	// Но этого быть не может по построению нашего дерева. Поэтому d <= D.

	// Предположим, что d == D. Но и этого не может быть, т.к наш алгоритм работает так, чт оон ВСЕГДА выбираем самую длинную цепь и подцепляет ее
	// а нам пришлось подсоединить еще одну цепь на цровень d, чтобы довести значение белых вершин до X.

	// предположим, что D == d + 1.
	// Этого тоже не может быть практически по тем же соображений что и в предыдущем пункте. Т.к мы подцепили звено на уровне d, то увеличить
	// количество белых вершин мы сможем только на уровне d + 2.

	// т.е. D >= d + 2, но это означает, что на любом шаге нашего алгоритма у нас результат не хуже чем у оптимального (у нас тоже уровень находится
	// не ниже чем на d + 2, но за счет того, что у нас всегда уменьшается количсетво звеньев мы точно не уступаем оптимальному алгоритму.

	// пусть cnt[i] - количество белых вершин на уровне i
	// Стоит задача найти наименьшее i=it такое, что SUM(cnt[i], i <= it) >= k
	// Таким образом, алгоритм решения такой:

	// Сортируем все звенья в DESC порядке по длине
	// Берем максимальный и вешаем на дерево
	// Обновляем cnt[i], для всех i, что лежат ниже точки присоединения нового звена (это можно сделать за LogN с помощью дерева отрезков)
	// Проверяем, можем ли мы найти такое it, что SUM(cnt[i], i <= it) >= k (тоже за LOGN)

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	sort(a, a + n);
	int level = 0;
	R = INF;

	int n2 = a[n - 1] + 500;

	// нужно добавить корневую вершину на 0-ой уровен.
	update(1, 0, n2, 0, 0, 1);

	for (int i = n - 1; i >= 0; i--)
	{
		// т.к мы всегда прикрепляем звенья как можно выше, то смотрим, если на уровне level у нас не осталось больше белых вершин,
		// то переходим на уровень ниже
		while (get(1, 0, n2, 0, level) == 0)
			level++;

		// убираем одну вершину с уровня level
		update(1, 0, n2, level, level, -1);

		// т.к каждая цепь разбивается "примерно пополам", то добавляем обе части:
		update(1, 0, n2, level + 2, level + 2 + (a[i] - 1) / 2 - 1, 1);
		update(1, 0, n2, level + 2, level + 2 + a[i] / 2 - 1, 1);

		R = min(R, search(1, 0, n2, k));
	}

	if (R == INF)
		R = -1;

	cout << R << endl;

	return 0;
}

```