E. Кевин и И
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Кевина есть целочисленная последовательность $$$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$$$ операций.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n, m, k$$$ ($$$1\leq n \leq 10^5$$$, $$$1\leq m \leq 10$$$, $$$0\leq k\leq nm$$$) — длина $$$a$$$, количество типов магии и максимальное количество операций.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i < 2^{30}$$$).

Третья строка содержит $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ ($$$0\leq b_i < 2^{30}$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимально возможную сумму последовательности $$$a$$$ после выполнения не более $$$k$$$ операций.

Пример
Входные данные
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
Примечание

В первом наборе входных данных возможна такая последовательность операций:

  • Сделать $$$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]$$$.