#include <iostream>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <array>
#include <cassert>
#include <stack>
#include <numeric>

#define endl '\n'
#define sync_cin                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define repi(i, a, b) for(int i = a; i <= (b); ++i)
#define rev(i, a, b) for(int i = a; i > (b); --i)
#define revi(i, a, b) for(int i = a; i >= (b); --i)
#define trav(a, x) for(auto& a : x)
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
#define DEBUG(x) std::cerr << #x"=" << x << endl

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;

//-----------------------------------------------------------------------------

template<typename T>
inline istream& operator>>(istream& is, vector<T>& v) {
  for (int ii = 0; ii < sz(v); ++ii) {
    is >> v[ii];
  }
  return is;
}

template<typename T>
inline ostream& operator<<(ostream& os, vector<T>& v) {
  for (int ii = 0; ii < sz(v); ++ii) {
    os << v[ii] << " ";
  }
  return os;
}

template<typename T1, typename T2>
inline istream& operator>>(istream& is, pair<T1, T2>& p) {
  is >> p.first >> p.second;
  return is;
}

template<typename T1, typename T2>
inline ostream& operator<<(ostream& os, pair<T1, T2>& p) {
  os << p.first << " " << p.second;
  return os;
}


template<typename T>
inline ostream& operator<<(ostream& os, vector<vector<T>>& mat) {
  for (int ii = 0; ii < sz(mat); ++ii) {
    for (int jj = 0; jj < sz(mat[0]); ++jj) {
      os << mat[ii][jj] << " ";
    }
    os << endl;
  }
  return os;
}

template<typename it>
void compress(it start, it end) {
  typedef typename remove_reference<decltype(*start)>::type T;
  map<T, vector<it>> m;
  for (it ii = start; ii != end; ii++) {
    m[*ii].push_back(ii);
  }
  int t = 0;
  for (auto& [x, v] : m) {
    for (auto& i : v) {
      *i = t;
    }
    ++t;
  }
}

//-----------------------------------------------------------------------------
template<typename T, typename U> 
struct LazySegTree {  
  // Segment tree with lazy prop.
  // T defines the node type, which should define operator + for combining two
  // nodes.
  // U defines the update type, which should define operators:
  //   - operator()(T node) returns node after applying this update to it.
  //   - operator+(U other) returns this update combined with another update.
  //
  // All operations are zero based.
  // size is size of the input array, tree is going to be of size 2*size.
  int size, height;

  // Represents zero node.
  T zero;

  // values represent tree nodes. dirty is true if some node has unapplied
  // update pending. updates are updates waiting to be applied.
  // root = values[1].
  vector<T> values;
  vector<bool> dirty;
  vector<U> updates;

  // Placeholder type for noop.
  U noop;

  LazySegTree(int size_, T zero_ = T(), U noop_ = U()) {
    zero = zero_;
    noop = noop_;
    size = size_;

    for (size = 1, height = 1; size < size_;) {
      size *= 2;
      ++height;
    }

    values.resize(2 * size, zero);
    dirty.resize(2 * size, false);
    updates.resize(2 * size, noop);
  }

  void SetLeaves(const vector<T>& leaves_) {
    copy(all(leaves_), values.begin() + size);
    fill(values.begin() + size + leaves_.size(), values.end(), zero);

    for (int i = size - 1; i > 0; --i) {
      values[i] = values[i * 2] + values[i * 2 + 1];
    }
  }

  void Apply(int i, U update) {
    // Apply update to this node.
    values[i] = update(values[i]);
    if (i < size) {
      // It is a tree node.
      // Store this update for later propagation.
      dirty[i] = true;
      updates[i] = updates[i] + update;
    }
  }

  void Rebuild(int i) {
    // Rebuild tree from this node upwards.
    for (int l = i / 2; l; l >>= 1) {
      T comb = values[l * 2] + values[l * 2 + 1];
      values[l] = updates[l](comb);
    }
  }

  void Propagate(int i) {
    for (int h = height; h; --h) {
      int node_idx = i >> h;
      if (dirty[node_idx]) {
        // Node above is dirty, push its update down.
        Apply(2 * node_idx, updates[node_idx]);
        Apply(2 * node_idx + 1, updates[node_idx]);

        updates[node_idx] = noop;
        dirty[node_idx] = false;
      }
    }
  }

  // Updates range [i, j].
  void Update(int i, int j, U update) {
    // - Modify indexes to point to leaves.
    // - Go up and propagate down updates on their path to the root.
    i += size, j += size;
    Propagate(i), Propagate(j);

    // This for goes up until indices converge to each other.
    for (int l = i, r = j; l <= r; l >>= 1, r >>= 1) {
      // These assume l and r are inclusive.
      // For example if we want to update [l, r), then we would write:
      // if (r & 1) instead. This is due to indexing in seg tree.
      // After update we have to post-increment/decrement so the next loop
      // iteration goes to the correct parent.
      if ((l & 1) == 1) Apply(l++, update);
      if ((r & 1) == 0) Apply(r--, update);
    }
    
    // We might need to update more nodes on the path to the root.
    // Notice that parent of nodes i/j might be left with some lazy update
    // pending on it. This is fine as we will apply it when we need it.
    Rebuild(i), Rebuild(j);
  }

  T Query(int i, int j) {
    i += size, j += size;
    Propagate(i), Propagate(j);

    T res_left = zero, res_right = zero;
    for (; i <= j; i >>= 1, j >>= 1) {
      if ((i & 1) == 1) res_left = res_left + values[i++];
      if ((j & 1) == 0) res_right = values[j--] + res_right;
    }
    return res_left + res_right;
  }

  // Returns right bound of the prefix [0, r] such that sum is at least x.
  int PrefixSumAtLeast(ll x) {
    int v = 1;
    int l = size;
    int r = 2 * size - 1;
    return PrefixSumAtLeastInternal(v, l, r, x) - size;
  }
  
  // Binary search over tree.
  int PrefixSumAtLeastInternal(int v, int l, int r, ll x) {
    // cout << v << " [" << l << " " << r << "]" << endl;
    if (l == r) return l;
    else {
      int m = (l + r) / 2;
      Propagate(l);
      Propagate(r);
      if (values[v * 2].val >= x) {
        return PrefixSumAtLeastInternal(v * 2, l, m, x);
      } else {
        return
          PrefixSumAtLeastInternal(v * 2 + 1, m + 1, r, x - values[2 * v].val);
      }
    }
  }
};


struct Node {
  /* data */ 
  ll val;
  int width;

  Node() {}
  Node(ll _v, int _w) : val(_v), width(_w) {}

  Node operator+(const Node& other) {
    return {val + other.val, width + other.width};
  }

  bool operator==(const Node& other) const {
    // not implemented.
    return true;
  }
};

struct Update {
  // add val to all in range [l, r].
  ll val;

  Node operator()(const Node& node) {
    return {node.val + node.width * val, node.width};
  }

  Update operator+(const Update& other) {
    return {val + other.val};
  }
};

void solve_case() {
  int n, k;
  cin >> n >> k;

  vector<int> l(n);
  cin >> l;
  ll S = 0;
  rep(i, 0, n) S += l[i] - 2;
  if (S + 1 < k) {
    cout << -1 << endl;
    return;
  }
  sort(all(l), greater<int>());

  int sz = l[0] + 1000;
  LazySegTree<Node, Update> seg_tree(sz, {0, 0}, {0});
  seg_tree.SetLeaves(vector<Node>(sz, Node(0, 1)));

  seg_tree.Update(0, 0, {1});

  int depth = 0;
  int ans = TYPEMAX(int);
  rep(i, 0, n) {
    while (seg_tree.Query(0, depth).val <= 0) depth++;

    seg_tree.Update(depth, depth, {-1});
    seg_tree.Update(depth + 2, depth + 1 + l[i] / 2, {1});
    seg_tree.Update(depth + 2, depth + 1 + (l[i] - 1) / 2, {1});

    if (seg_tree.values[1].val >= k) {
      ans = min(ans, seg_tree.PrefixSumAtLeast(k));
    }
  }

  cout << ans << endl;
}

int main() {
  sync_cin;

  // int t; cin >> t;
  int t = 1;
  while (t--) {
    solve_case();
  }
  return 0;
}

### Prompt

Create a solution in CPP for the following problem:

// 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 <vector>
#include <stdio.h>
#include <cstdlib>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <array>
#include <cassert>
#include <stack>
#include <numeric>

#define endl '\n'
#define sync_cin                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define repi(i, a, b) for(int i = a; i <= (b); ++i)
#define rev(i, a, b) for(int i = a; i > (b); --i)
#define revi(i, a, b) for(int i = a; i >= (b); --i)
#define trav(a, x) for(auto& a : x)
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
#define DEBUG(x) std::cerr << #x"=" << x << endl

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;

//-----------------------------------------------------------------------------

template<typename T>
inline istream& operator>>(istream& is, vector<T>& v) {
  for (int ii = 0; ii < sz(v); ++ii) {
    is >> v[ii];
  }
  return is;
}

template<typename T>
inline ostream& operator<<(ostream& os, vector<T>& v) {
  for (int ii = 0; ii < sz(v); ++ii) {
    os << v[ii] << " ";
  }
  return os;
}

template<typename T1, typename T2>
inline istream& operator>>(istream& is, pair<T1, T2>& p) {
  is >> p.first >> p.second;
  return is;
}

template<typename T1, typename T2>
inline ostream& operator<<(ostream& os, pair<T1, T2>& p) {
  os << p.first << " " << p.second;
  return os;
}


template<typename T>
inline ostream& operator<<(ostream& os, vector<vector<T>>& mat) {
  for (int ii = 0; ii < sz(mat); ++ii) {
    for (int jj = 0; jj < sz(mat[0]); ++jj) {
      os << mat[ii][jj] << " ";
    }
    os << endl;
  }
  return os;
}

template<typename it>
void compress(it start, it end) {
  typedef typename remove_reference<decltype(*start)>::type T;
  map<T, vector<it>> m;
  for (it ii = start; ii != end; ii++) {
    m[*ii].push_back(ii);
  }
  int t = 0;
  for (auto& [x, v] : m) {
    for (auto& i : v) {
      *i = t;
    }
    ++t;
  }
}

//-----------------------------------------------------------------------------
template<typename T, typename U> 
struct LazySegTree {  
  // Segment tree with lazy prop.
  // T defines the node type, which should define operator + for combining two
  // nodes.
  // U defines the update type, which should define operators:
  //   - operator()(T node) returns node after applying this update to it.
  //   - operator+(U other) returns this update combined with another update.
  //
  // All operations are zero based.
  // size is size of the input array, tree is going to be of size 2*size.
  int size, height;

  // Represents zero node.
  T zero;

  // values represent tree nodes. dirty is true if some node has unapplied
  // update pending. updates are updates waiting to be applied.
  // root = values[1].
  vector<T> values;
  vector<bool> dirty;
  vector<U> updates;

  // Placeholder type for noop.
  U noop;

  LazySegTree(int size_, T zero_ = T(), U noop_ = U()) {
    zero = zero_;
    noop = noop_;
    size = size_;

    for (size = 1, height = 1; size < size_;) {
      size *= 2;
      ++height;
    }

    values.resize(2 * size, zero);
    dirty.resize(2 * size, false);
    updates.resize(2 * size, noop);
  }

  void SetLeaves(const vector<T>& leaves_) {
    copy(all(leaves_), values.begin() + size);
    fill(values.begin() + size + leaves_.size(), values.end(), zero);

    for (int i = size - 1; i > 0; --i) {
      values[i] = values[i * 2] + values[i * 2 + 1];
    }
  }

  void Apply(int i, U update) {
    // Apply update to this node.
    values[i] = update(values[i]);
    if (i < size) {
      // It is a tree node.
      // Store this update for later propagation.
      dirty[i] = true;
      updates[i] = updates[i] + update;
    }
  }

  void Rebuild(int i) {
    // Rebuild tree from this node upwards.
    for (int l = i / 2; l; l >>= 1) {
      T comb = values[l * 2] + values[l * 2 + 1];
      values[l] = updates[l](comb);
    }
  }

  void Propagate(int i) {
    for (int h = height; h; --h) {
      int node_idx = i >> h;
      if (dirty[node_idx]) {
        // Node above is dirty, push its update down.
        Apply(2 * node_idx, updates[node_idx]);
        Apply(2 * node_idx + 1, updates[node_idx]);

        updates[node_idx] = noop;
        dirty[node_idx] = false;
      }
    }
  }

  // Updates range [i, j].
  void Update(int i, int j, U update) {
    // - Modify indexes to point to leaves.
    // - Go up and propagate down updates on their path to the root.
    i += size, j += size;
    Propagate(i), Propagate(j);

    // This for goes up until indices converge to each other.
    for (int l = i, r = j; l <= r; l >>= 1, r >>= 1) {
      // These assume l and r are inclusive.
      // For example if we want to update [l, r), then we would write:
      // if (r & 1) instead. This is due to indexing in seg tree.
      // After update we have to post-increment/decrement so the next loop
      // iteration goes to the correct parent.
      if ((l & 1) == 1) Apply(l++, update);
      if ((r & 1) == 0) Apply(r--, update);
    }
    
    // We might need to update more nodes on the path to the root.
    // Notice that parent of nodes i/j might be left with some lazy update
    // pending on it. This is fine as we will apply it when we need it.
    Rebuild(i), Rebuild(j);
  }

  T Query(int i, int j) {
    i += size, j += size;
    Propagate(i), Propagate(j);

    T res_left = zero, res_right = zero;
    for (; i <= j; i >>= 1, j >>= 1) {
      if ((i & 1) == 1) res_left = res_left + values[i++];
      if ((j & 1) == 0) res_right = values[j--] + res_right;
    }
    return res_left + res_right;
  }

  // Returns right bound of the prefix [0, r] such that sum is at least x.
  int PrefixSumAtLeast(ll x) {
    int v = 1;
    int l = size;
    int r = 2 * size - 1;
    return PrefixSumAtLeastInternal(v, l, r, x) - size;
  }
  
  // Binary search over tree.
  int PrefixSumAtLeastInternal(int v, int l, int r, ll x) {
    // cout << v << " [" << l << " " << r << "]" << endl;
    if (l == r) return l;
    else {
      int m = (l + r) / 2;
      Propagate(l);
      Propagate(r);
      if (values[v * 2].val >= x) {
        return PrefixSumAtLeastInternal(v * 2, l, m, x);
      } else {
        return
          PrefixSumAtLeastInternal(v * 2 + 1, m + 1, r, x - values[2 * v].val);
      }
    }
  }
};


struct Node {
  /* data */ 
  ll val;
  int width;

  Node() {}
  Node(ll _v, int _w) : val(_v), width(_w) {}

  Node operator+(const Node& other) {
    return {val + other.val, width + other.width};
  }

  bool operator==(const Node& other) const {
    // not implemented.
    return true;
  }
};

struct Update {
  // add val to all in range [l, r].
  ll val;

  Node operator()(const Node& node) {
    return {node.val + node.width * val, node.width};
  }

  Update operator+(const Update& other) {
    return {val + other.val};
  }
};

void solve_case() {
  int n, k;
  cin >> n >> k;

  vector<int> l(n);
  cin >> l;
  ll S = 0;
  rep(i, 0, n) S += l[i] - 2;
  if (S + 1 < k) {
    cout << -1 << endl;
    return;
  }
  sort(all(l), greater<int>());

  int sz = l[0] + 1000;
  LazySegTree<Node, Update> seg_tree(sz, {0, 0}, {0});
  seg_tree.SetLeaves(vector<Node>(sz, Node(0, 1)));

  seg_tree.Update(0, 0, {1});

  int depth = 0;
  int ans = TYPEMAX(int);
  rep(i, 0, n) {
    while (seg_tree.Query(0, depth).val <= 0) depth++;

    seg_tree.Update(depth, depth, {-1});
    seg_tree.Update(depth + 2, depth + 1 + l[i] / 2, {1});
    seg_tree.Update(depth + 2, depth + 1 + (l[i] - 1) / 2, {1});

    if (seg_tree.values[1].val >= k) {
      ans = min(ans, seg_tree.PrefixSumAtLeast(k));
    }
  }

  cout << ans << endl;
}

int main() {
  sync_cin;

  // int t; cin >> t;
  int t = 1;
  while (t--) {
    solve_case();
  }
  return 0;
}

```