← 返回题目列表

Codeforces · 748/E

E. 圣诞老人和橘子

中文机器翻译题面 查看原题

圣诞老人有 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 片。