← 返回题目列表

Codeforces · 2011/H

H. 奇怪的矩阵

中文机器翻译题面 查看原题

给定一个矩阵 $$$a$$$,大小为 $$$n \times m$$$,由从 $$$0$$$ 到 $$$31$$$ 的整数组成。

如果对于每两个不同的行 $$$i$$$ 和 $$$j$$$,以下两个条件均成立,我们称该矩阵为奇怪矩阵:

- 对于每组 $$$k$$$ 索引 $$$(x_1, x_2, \dots, x_k)$$$,其中 $$$1 \le x_1 < x_2 < \cdots < x_k \le m$$$,等式 $$$a_{i, x_1} \mathbin{\&} a_{j, x_1} \mathbin{\&} a_{i, x_2} \mathbin{\&} a_{j, x_2} \mathbin{\&} \cdots \mathbin{\&} a_{i, x_k} \mathbin{\&} a_{j, x_k} = 0$$$ 成立(其中 $$$\mathbin{\&}$$$ — 两个数字的按位与);
- 对于每组 $$$k$$$ 索引 $$$(x_1, x_2, \dots, x_k)$$$,其中 $$$1 \le x_1 < x_2 < \cdots < x_k \le m$$$,等式 $$$a_{i, x_1} \mathbin{|} a_{j, x_1} \mathbin{|} a_{i, x_2} \mathbin{|} a_{j, x_2} \mathbin{|} \cdots \mathbin{|} a_{i, x_k} \mathbin{|} a_{j, x_k} = 31$$$ 成立(其中 $$$\mathbin{|}$$$ — 两个数字的按位或)。

您可以执行任意多次以下操作:取矩阵的任意行和从 $$$0$$$ 到 $$$31$$$ 之间的数字 $$$y$$$;然后将数字 $$$y$$$ 按位异或应用于所选行的所有元素。这种操作的成本等于$$$y$$$。

你的任务是计算使矩阵变得奇怪的最小成本,或者报告这是不可能的。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$1 \le n, m \le 50$$$; $$$1 \le k \le m$$$)。

接下来,有 $$$n$$$ 行,其中第 $$$i$$$ 行包含 $$$m$$$ 整数 $$$a_{i, 1}, a_{i, 2}, \dots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le 31$$$)。

输出

对于每个测试用例,输出一个整数 - 使矩阵变得奇怪的最小成本,如果不可能使矩阵变得奇怪,则输出 -1。

示例

输入 #1

3
2 3 1
0 1 0
1 0 1
3 2 2
0 1
2 3
4 5
5 5 5
0 5 17 4 22
8 5 16 21 9
7 25 31 30 8
0 0 5 15 13
1 2 3 4 5

输出 #1

30
-1
24