У вас есть \(n\) прямоугольников, \(i\)-й из которых имеет ширину \(a_i\) и высоту \(b_i\).
Вы можете неограниченное количество раз выполнить следующую операцию: выбрать прямоугольник и клетку в нём, а затем закрасить её.
Каждый раз, когда вы закрашиваете целиком какую-либо строку или столбец, вы получаете \(1\) балл. Ваша задача — набрать хотя бы \(k\) баллов за как можно меньшее число операций.
Допустим, у вас есть прямоугольник ширины \(6\) и высоты \(3\). Вы можете набрать \(4\) очка, закрасив все клетки в \(4\)-х любых столбцах, выполнив таким образом \(12\) операций.
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимое для того, чтобы набрать хотя бы \(k\) очков. Если набрать хотя бы \(k\) очков невозможно, выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
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
|