圣诞老人有 n 个橘子,其中第 i 个橘子正好由 ai 片组成。圣诞老人来到一所有 k 个学生的学校。圣诞老人决定用橘子招待他们。
然而,橘子的数量可能太少,无法向每个学生展示至少一个橘子。因此,圣诞老人决定将橘子分成几部分,这样就不会冒犯任何人。为了做到这一点,他可以将一个橘子或任何现有的部分分成两个较小的相等部分。如果他想要分割的部分中的切片数量是奇数,那么所得到的部分将比另一个部分多一个切片。禁止分割仅由一个切片组成的部分。
圣诞老人想要向每个人展示整个橘子或其中的一部分(这也意味着每个人都必须获得正数的橘子片)。一个或几个橘子或其部分可能会留在圣诞老人身边。
设bi为第i个瞳孔最终拥有的切片数。让圣诞老人的快乐成为所有双性人中最低限度的。
你的任务是找到圣诞老人用橘子(或其部分)款待每个人后所能获得的最大快乐。
输入
第一行包含两个正整数 n 和 k (1 ≤ n ≤ 106, 1 ≤ k ≤ 2·109),分别表示橘子的数量和学生的数量。
第二行由 n 个正整数 a1, a2, ..., an (1 ≤ ai ≤ 107) 组成,其中 ai 代表第 i 个橘子的片数。
输出
如果无法向每个人展示一个橘子或橘子的一部分,请打印 -1。否则,打印圣诞老人可以拥有的最大可能的快乐。
示例
输入 #1
3 2 5 9 3
输出 #1
5
输入 #2
2 4 12 14
输出 #2
6
输入 #3
2 3 1 1
输出 #3
-1
注意
在第一个示例中,圣诞老人应将第二个橘子分成两部分,分别为 5 片和 4 片。之后,他可以将有 5 片的部分呈现给第一个学生,将整个第一个橘子(也有 5 片)呈现给第二个学生。
在第二个示例中,圣诞老人应该将两个橘子分开,这样他就能够呈现两部分 6 片和两部分 7 片。
在第三个示例中,圣诞老人无法以每个人都拥有任何东西的方式向 3 个学生赠送 2 片。