CF2061E Kevin and And

题目描述

Kevin 有一个长度为 n n n 的整数序列 a a a 。同时，Kevin 拥有 m m m 种魔法类型，其中第 i i i 种魔法可以用整数 b i b_i b i ​ 表示。

Kevin 最多可以执行 k k k 次（可能为零）魔法操作。每次操作中，Kevin 可以执行以下步骤：

  • 选择两个索引 i i i （ 1 ≤ i ≤ n 1 \leq i \leq n 1 ≤ i ≤ n ）和 j j j （ 1 ≤ j ≤ m 1 \leq j \leq m 1 ≤ j ≤ m ），然后将 a i a_i a i ​ 更新为 a i   &   b j a_i\ \&\ b_j a i ​ & b j ​ 。此处 & \& & 表示 。

请计算在执行最多 k k k 次操作后，序列 a a a 中所有数的最小可能总和。

输入格式

每个测试包含多个测试用例。第一行包含测试用例数量 t t t （ 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1 ≤ t ≤ 1 0 4 ）。接下来是测试用例描述。

每个测试用例的第一行包含三个整数 n , m , k n, m, k n , m , k （ 1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5