Kevin は長さ $n$ の整数列 $a$ を持っています。また、Kevin は $m$ 種類の魔法を持っており、$i$ 番目の魔法は整数 $b_i$ で表されます。
Kevin は最大で $k$ 回（0回でもよい）魔法を使用できます。各操作において、Kevin は以下のことができます。
- 2つの添字 $i$ ($1 \le i \le n$) と $j$ ($1 \le j \le m$) を選び、$a_i$ を $a_i \& b_j$ に更新する。ここで、$\&$ はビットごとの AND 演算を表します。
最大 $k$ 回の操作を行った後の、数列 $a$ のすべての要素の和の最小値を求めてください。
入力
各テストケースには複数のテストケースが含まれます。最初の行にはテストケースの数 $t$ ($1 \le t \le 10^4$) が含まれます。
各テストケースの記述は以下の通りです。
各テストケースの最初の行には、3つの整数 $n, m, k$ ($1 \le n \le 10^5, 1 \le m \le 10, 0 \le k \le nm$) が含まれます。これらは $a$ の長さ、$m$ 種類の魔法の数、および最大操作回数を表します。
2行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{30}$) が含まれます。
3行目には、$m$ 個の整数 $b_1, b_2, \dots, b_m$ ($0 \le b_i < 2^{30}$) が含まれます。
すべてのテストケースにおける $n$ の総和は $10^5$ を超えないことが保証されています。
出力
各テストケースについて、最大 $k$ 回の操作を行った後の数列 $a$ の要素の和の最小値を1つの整数として出力してください。
入出力例
入力 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
1 3 11 5368709115 0
注記
最初のテストケースにおいて、考えられる手順の1つは以下の通りです。
- $a_1$ を $a_1 \& b_1$ に更新する。数列は $[5]$ になる。
- $a_1$ を $a_1 \& b_3$ に更新する。数列は $[1]$ になる。
2番目のテストケースにおいて、考えられる手順の1つは以下の通りです。
- $a_1$ を $a_1 \& b_3$ に更新する。数列は $[1, 6]$ になる。
- $a_2$ を $a_2 \& b_3$ に更新する。数列は $[1, 2]$ になる。