题目描述

小 W 有 $n$ 个山竹，其中第 $i$ 个山竹有 $a_i$ 片。小 W 来到一所小学，学校有 $k$ 名学生，他决定用山竹给他们增加一些营养。

然而，山竹的数量可能太少，无法给每个学生哪怕一整个山竹。因此，小 W 决定把山竹分成几份，这样就不会有人生气了。为了做到这一点，他可以把一个山竹或任何现有的部分分成两个较小的相等部分。如果他想分割的部分的片数是奇数，那么产生的两个小份中就会有一个比另一个多出一片。但不允许将只有一片的部分分割。

小 W 想送给每个人一个完整的山竹或者正好是它的一部分（每个人都必须得到一个正数的小片，并且不允许多个山竹的小片合成一份）。一个或几个山竹或它们的一部分可以留在小 W 那里。

假设 $b_i$ 是第 $i$ 个学生最后拥有的山竹片数，小 W 的快乐度是所有 $b_i$ 的最小值。

你的任务是找出小 W 可能拥有的最大快乐值。

输入格式

第一行，两个正整数 $n$ 和 $k$，表示山竹和学生的数量。

第二行，$n$ 个正整数 $a_1,a_2,\cdots, a_n$，$a_i$ 表示第 $i$ 个山竹的片数。

输出格式

如果没有办法把山竹或山竹的一部分送给大家，就输出 -1。否则，输出小 W 可能拥有的最大快乐值。

样例

3 2
5 9 3

5

2 4
12 14

6

2 3
1 1

-1

样例解释

在第一个例子中，小 W 应该把第二个山竹分成两部分，分别是 $5$ 片和 $4$ 片。然后，他可以把有 $5$ 片的部分送给第一个学生，把第一个山竹整个（也有 $5$ 片）送给第二个学生。

在第二个例子中，小 W 应该把两个山竹分开，这样他就可以把两个有 $6$ 片的部分和两个有 $7$ 片的部分交给学生。

在第三个例子中，小 W 不可能把两片山竹分给三个学生。

数据范围

$16\%$ 的数据， $1\le n ≤ 5, 1\le k ≤ 6$；

$32\%$ 的数据， $1\le n ≤ 50,1\le k ≤ 300$；

$44\%$ 的数据， $1\le n ≤ 5000, k ≤ 2\times10^9$；

$100\%$ 的数据， $1 ≤ n ≤ 10^6，1 ≤ k ≤ 2\times10^9，1 ≤ a_i ≤ 10^7$。