Codeforces Round 966 (Div. 3) |
---|
Finished |
You have $$$n$$$ rectangles, the $$$i$$$-th of which has a width of $$$a_i$$$ and a height of $$$b_i$$$.
You can perform the following operation an unlimited number of times: choose a rectangle and a cell in it, and then color it.
Each time you completely color any row or column, you earn $$$1$$$ point. Your task is to score at least $$$k$$$ points with as few operations as possible.
Suppose you have a rectangle with a width of $$$6$$$ and a height of $$$3$$$. You can score $$$4$$$ points by coloring all the cells in any $$$4$$$ columns, thus performing $$$12$$$ operations.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The following are the descriptions of the test cases.
The first line of each test case description contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 1000, 1 \le k \le 100$$$) — the number of rectangles in the case and the required number of points.
The next $$$n$$$ lines contain the descriptions of the rectangles. The $$$i$$$-th line contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 100$$$) — the width and height of the $$$i$$$-th rectangle.
It is guaranteed that the sum of the values of $$$n$$$ across all test cases does not exceed $$$1000$$$.
For each test case, output a single integer — the minimum number of operations required to score at least $$$k$$$ points. If it is impossible to score at least $$$k$$$ points, output -1.
71 46 31 54 45 101 11 11 11 11 12 1001 25 63 112 23 34 43 259 24 38 104 185 48 58 36 2
12 14 5 -1 17 80 35
Name |
---|