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.