← 返回题目
题库练习 矩形涂色
← 上一题 下一题 →

A6980 | 矩形涂色

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

你有 $n$ 个矩形，第 $i$ 个矩形的宽度为 $a_i$，高度为 $b_i$。

你可以无限次地执行这个操作：

选择其中的一个矩形并为其矩形内的一个单元格着色。

当每次有任意一个矩形内的一行或一列被完全着色，你都可以获得 $1$ 分。你的任务是去用尽量少的操作次数来获得至少 $k$ 的得分

假设有一个宽度为 $6$，高度为 $3$ 的矩形，你可以对矩形中的任意四列着色，从而使用 $12$ 次操作，获得 $4$ 分

输入格式

第一行是一个整数 $t$，表示一共有 $t$ 组数据。

每个测试用例的第一行是两个整数 $n$ 和 $k$，表示共有 $n$ 个矩形，$k$ 的意思同上文所说。

接下来的 $n$ 行包含对矩形的描述，第 $i$ 行是两个整数 $a_i$ 和 $b_i$，表示一个矩形的宽和高。

输出格式

对于每个测试用例，输出一个整数表示要获得至少 $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
C++ 编辑器
输入
输出