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 .