← 返回题目列表

Codeforces · 2000/F

F. 颜色行和列

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

您有 $$$n$$$ 个矩形,其中第 $$$i$$$ 的宽度为 $$$a_i$$$,高度为 $$$b_i$$$。

您可以无限次执行以下操作:选择一个矩形和其中的一个单元格,然后为其着色。

每次完成任何行或列的着色,您将获得 $$$1$$$ 积分。您的任务是通过尽可能少的操作获得至少 $$$k$$$ 分。

假设您有一个宽度为 $$$6$$$ 且高度为 $$$3$$$ 的矩形。您可以通过为任何 $$$4$$$ 列中的所有单元格着色来获得 $$$4$$$ 分,从而执行 $$$12$$$ 操作。

输入

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

每个测试用例描述的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 1000, 1 \le k \le 100$$$) — 用例中矩形的数量和所需点数。

接下来的 $$$n$$$ 行包含矩形的描述。第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 100$$$) — 第 $$$i$$$ 矩形的宽度和高度。

保证所有测试用例的 $$$n$$$ 值的总和不超过 $$$1000$$$。

输出

对于每个测试用例,输出一个整数 - 获得至少 $$$k$$$ 分所需的最少操作数。如果不可能获得至少 $$$k$$$ 分,则输出 -1。

示例

输入 #1

7
1 4
6 3
1 5
4 4
5 10
1 1
1 1
1 1
1 1
1 1
2 100
1 2
5 6
3 11
2 2
3 3
4 4
3 25
9 2
4 3
8 10
4 18
5 4
8 5
8 3
6 2

输出 #1

12
14
5
-1
17
80
35