CF2000F Color Rows and Columns

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.