F. Закрась строки и столбцы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$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.

Пример
Входные данные
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
Выходные данные
12
14
5
-1
17
80
35