Марчин — тренер в университете. Есть \(n\) студентов, которые хотят поучаствовать в сборах. Марчин умный тренер, поэтому он хочет отправить только студентов, которые могут спокойно работать вместе.
Рассмотрим студентов. Они пронумерованы целыми числами от \(1\) до \(n\). Каждый из них описывается двумя целыми числами \(a_i\) и \(b_i\); \(b_i\) равно опыту \(i\)-го участника (чем больше, тем лучше). А также есть \(60\) известных алгоритмов, которые пронумерованы целыми числами от \(0\) до \(59\). Если \(i\)-й студент знает \(j\)-й алгоритм, тогда \(j\)-й бит (\(2^j\)) равен единице в двоичной записи \(a_i\). Иначе, он равен нулю.
Студент \(x\) считает, что он лучше студента \(y\) если и только если \(x\) знает какой-то алгоритм, который не знает \(y\). Обратите внимание, что два студента могут считать, что они лучше друг друга. Группа студентов может работать спокойно, если ни один студент из группы не считает, что он лучше всех остальных в этой группе.
Марчин хочет отправить группу из хотя бы двух студентов, которые могут работать вместе и имеют максимально возможную сумму уровней опыта. Чему равна эта сумма?
Выходные данные
Выведите одно целое число, которое равно максимальной сумме \(b_i\) студентов в группе, в которой студенты могут работать спокойно. Если не существует группы из хотя бы двух студентов, в которой студенты могут работать спокойно, выведите 0.
Примечание
В первом примере оптимально отправить на сборы первого, второго, и третьего студента. Также возможно отправить только первого и третьего студента, но сумма \(b_i\) у них будет меньше.
Во втором тесте, в каждой группе из хотя бы двух студентов, кто-то всегда будет думать, что он лучше всех остальных в этой группе.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 2 3 6
2 8 5 10
|
15
|
|
2
|
3
1 2 3
1 2 3
|
0
|
|
3
|
1
0
1
|
0
|