← 返回题目列表

Codeforces · 2189/A

A. 带数字的表格

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

Peter 画了一张大小为 $$$h \times l$$$ 的表格,其中填满了零。我们将其行从上到下编号为 $$$1$$$ 到 $$$h$$$,列编号从左到右从 $$$1$$$ 到 $$$l$$$。 Ned 提出了一个数字数组 $$$a_1, a_2, \ldots, a_n$$$ 并想要修改该表。

Ned 可以从他的数组中选择 $$$2k \leq n$$$ 个数字,并将它们分成 $$$k$$$ 对。之后,对于每个结果对 $$$x, y$$$,他获取位于 $$$x$$$ 行和 $$$y$$$ 列中的单元格,并将 $$$1$$$ 添加到该单元格中的数字。如果这样的单元格不存在,则该对对表不执行任何操作。

Peter支持Ned的倡议,并要求他最大化表中数字的总和。帮助内德了解他能达到的最大金额是多少。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$h$$$ 和 $$$l$$$ ($$$2 \le n \le 100$$$, $$$1 \le h, l \le 1000$$$) - 分别是数组的大小、表格的高度和表格的宽度。

每个测试用例的第二行包含 $$$n$$$ 数字 $$$a_1$$$、$$$a_2$$$、$$$\ldots$$$、$$$a_n$$$ ($$$1 \le a_i \le 1000$$$) — 数组本身。

输出

对于每个测试用例,输出表中数字的最大可能总和。

示例

输入
复制

7
2 1 1
1 1
5 2 2
1 2 2 3 2
8 4 2
7 2 2 2 3 4 4 2
7 3 6
10 4 1 3 5 4 6
2 4 4
5 5
7 6 3
10 4 1 3 5 4 6
4 1 1
1 1 1 1

输出
复制

1
2
3
2
0
2
2

注意

在第一个测试用例中,Ned 可以采用 $$$(1, 1)$$$ 对并将 $$$1$$$ 添加到位于 $$$1$$$ 行和 $$$1$$$ 列的数字。

在第二个测试用例中,Ned 可以采用数字 $$$1, 2, 2, 2$$$ 并将它们按如下方式配对:$$$(1, 2), (2, 2)$$$。然后,在表格的两个单元格中,将有$$$1$$$,并且总和将等于$$$2$$$。可以证明,不可能获得更高的总和。

在第五个测试用例中,Ned 唯一可以选择的对是 $$$(5, 5)$$$。由于表格中不存在这样的单元格,因此表格中的数字总和不能超过$$$0$$$。

在第七个测试用例中,Ned 可以将数字配对如下:$$$(1, 1), (1, 1)$$$。那么表中唯一的单元格将包含数字$$$2$$$,总和也将是$$$2$$$。可以证明,不可能获得更高的总和。