У вас есть сумка размера \(n\). Так же у вас есть \(m\) коробок. Размер \(i\)-й коробки \(a_i\), где \(a_i\) — целая неотрицательная степень двойки.
Вы можете делить коробки на две части одинакового размера. Ваша задача — полностью заполнить сумку.
Например, если \(n = 10\) и \(a = [1, 1, 32]\), то вам нужно разделить коробку размера \(32\) на две части размера \(16\), а затем разделить коробку размера \(16\). Таким образом, вы сможете заполнить сумку коробками размеров \(1\), \(1\) и \(8\).
Посчитайте минимальное количество делений, которое придется сделать для заполнения сумки размера \(n\).
Выходные данные
На каждый набор входных данных выведите число — минимальное количество делений, которые придется сделать для заполнения сумки размера \(n\) (или \(-1\), если заполнить сумку невозможно).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
10 3
1 32 1
23 4
16 1 4 1
20 5
2 1 16 1 8
|
2
-1
0
|