У Санта-Клауса есть n мандаринов, причём i-й из них имеет ai долек. Санта-Клаус пришел в школу, где учится k учеников. Он решил угостить их мандаринами.
Так как на всех мандаринов может не хватить, Санта-Клаус решил поделить их на части, чтобы никто не обиделся. Для этого он может делить мандарины пополам, а также делить любую часть пополам. Если количество долек в мандарине или в части, которую Санта-Клаус делит, нечётное, то в одной получившейся части окажется на одну дольку больше, чем в другой. Делить мандарин или часть мандарина можно лишь в том случае, если после деления каждая получившаяся часть будет иметь хотя бы одну дольку.
Санта-Клаус хочет дать каждому из школьников ровно один мандарин или одну часть мандарина (в частности, каждый ученик должен получить положительное количество долек). Возможно, что у Санта-Клауса останется несколько мандаринов или частей после того, как он раздаст часть из них школьникам.
Пусть в результате угощения i-му ученику достанется bi долек. В таком случае радость Санта-Клауса будет равна минимальному значению среди всех bi.
Найдите максимальную возможную величину радости Санта-Клауса, которую он может получить после угощения учеников мандаринами.
Выходные данные
Если невозможно раздать всем ученикам по манадарину или части мандарина, выведите -1. В противном случае выведите максимально возможную величину радости Санта-Клауса.
Примечание
В первом примере Санта-Клаусу нужно разделить второй манадрин пополам, чтобы в одной части было 5 долек, а в другой 4. Тогда он сможет отдать одному ученику часть, в которой 5 долек, а второму целый первый манадарин, в котором также 5 долек.
Во втором примере Санта-Клаусу нужно разделить пополам оба манадрина, тогда он сможет отдать двум ученикам части по 6 долек, а двум другим ученикам — части по 7 долек.
В третьем примере Санта-Клаус не сможет дать всем ученикам хотя бы по одной дольке, так как у него есть всего 2 дольки и 3 ученика.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
5 9 3
|
5
|
|
2
|
2 4
12 14
|
6
|
|
3
|
2 3
1 1
|
-1
|