В местном бридж-клубе сейчас спорят на \(n\) различных тем, пронумерованных от \(0\) до \(n-1\), и, вот совпадение, в клубе состоят ровно \(2^n\) игроков, пронумерованных от \(0\) до \(2^n-1\). Никакие два игрока не имеют полностью совпадающих взглядов на все \(n\) тем, а именно, у \(i\)-го игрока положительный взгляд на \(j\)-ю тему, если \(i\ \&\ 2^j > 0\), и отрицательный взгляд иначе. Здесь \(\&\) обозначает операцию побитового И.
Вы хотите организовать турнир по бриджу, в котором примут участие не более чем \(k\) пар игроков (в бридж играют командами из двух игроков). Вы можете составлять пары игроков произвольным образом (каждый игрок должен быть не более чем в одной паре), но с одним условием: два игрока не могут быть в одной паре, если у них различные взгляды на \(2\) или более из данных \(n\) тем.
Вы знаете, что \(i\)-й игрок заплатит вам \(a_i\) долларов, если примет участие в турнире. Вычислите максимальную сумму, которую можно получить, выбрав команды оптимальным образом.
Выходные данные
Выведите одно целое число: максимальную сумму, которую вы можете получить, если составите команды оптимальным образом.
Примечание
В первом примере оптимальное решение — поставить в пару \(0\)-го и \(2\)-го игрока, что принесет \(8 + 5 = 13\) долларов. Хотя \(0\)-й и \(5\)-й игроки принесли бы вместе \(8 + 10 = 18\) долларов, мы их не можем объединить в команду, так как их взгляды отличаются в \(2\) из \(3\) тем.
Во втором примере можно объединить в команду \(0\)-го и \(1\)-го игрока, а также \(2\)-го и \(3\)-го игрока, что в сумме даст \(7 + 4 + 5 + 7 = 23\) долларов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
8 3 5 7 1 10 3 2
|
13
|
|
2
|
2 3
7 4 5 7
|
23
|
|
3
|
3 2
1 9 1 5 7 8 1 1
|
29
|