您有 $$$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