У Кевина есть целочисленная последовательность \(a\) длины \(n\). Также у Кевина есть \(m\) типов магии, где \(i\)-й тип магии может быть представлен целым числом \(b_i\).
Кевин может выполнить не более \(k\) (возможно, ноль) магических операций:
- Выбрать два индекса \(i\) (\(1\leq i\leq n\)) и \(j\) (\(1\leq j\leq m\)), а затем сделать \(a_i\) равным \(a_i\ \&\ b_j\). Здесь \(\&\) обозначает операцию побитового И.
Найдите минимально возможную сумму последовательности \(a\) после выполнения не более \(k\) операций.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимально возможную сумму последовательности \(a\) после выполнения не более \(k\) операций.
Примечание
В первом наборе входных данных возможна такая последовательность операций:
- Сделать \(a_1\) равным \(a_1\ \&\ b_1\). Последовательность станет равна \([5]\).
- Сделать \(a_1\) равным \(a_1\ \&\ b_3\). Последовательность станет равна \([1]\).
Во втором наборе входных данных возможна такая последовательность операций:
- Сделать \(a_1\) равным \(a_1\ \&\ b_3\). Последовательность станет равна \([1, 6]\).
- Сделать \(a_2\) равным \(a_2\ \&\ b_3\). Последовательность станет равна \([1, 2]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 3 2
7
5 6 3
2 3 2
5 6
5 6 3
10 2 5
3 1 4 1 5 9 2 6 5 3
7 8
5 1 0
1073741823 1073741823 1073741823 1073741823 1073741823
1073741823
1 1 0
0
0
|
1
3
11
5368709115
0
|