F. 给行和列涂色
每次测试的时间限制：$3$ 秒
每次测试的内存限制：$256$ 兆字节

你有 $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$ 行每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 100$）—— 第 $i$ 个矩形的宽度和高度。

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

输出
对于每个测试用例，输出一个整数 —— 获得至少 $k$ 分所需的最少操作次数。如果不可能获得至少 $k$ 分，则输出 $-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

输出

12
14
5
-1
17
80
35