E. Стога сена
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В следующее новолуние вселенная сбросится, начиная с Флориды. Мужчина из Флориды должен остановить это, но сначала ему нужно найти важный артефакт.

Есть $$$n$$$ стогов сена, пронумерованных от $$$1$$$ до $$$n$$$, где стог сена $$$i$$$ содержит $$$a_i$$$ тюков сена. Под одним из стогов сена возможно спрятана иголка, но вы не знаете, под каким именно. Ваша задача состоит в том, чтобы переместить тюки сена так, чтобы каждый стог сена был пустым хотя бы один раз, что позволит вам проверить, спрятана ли иголка под этим конкретным стогом сена.

Однако этот процесс не так прост. Как только стог сена $$$i$$$ будет опустошен в первый раз, ему будет присвоено ограничение по высоте, и он больше не сможет содержать более $$$b_i$$$ тюков сена. Более формально ход описывается следующим образом:

  • Выберите два стога сена $$$i$$$ и $$$j$$$. Если стог сена $$$i$$$ не был опустошен ранее или в стоге сена $$$i$$$ содержится строго меньше, чем $$$b_i$$$ тюков сена, вы можете переместить ровно $$$1$$$ тюк сена из стога $$$j$$$ в стог $$$i$$$.

Обратите внимание: Перед опустошением стога его высота не ограничена, и вы можете переместить в этот стог столько тюков, сколько захотите.

Найдите минимальное количество ходов, необходимых для того, чтобы каждый стог сена был опустошен хотя бы один раз, или сообщите, что это невозможно.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$2\le n\le 5\cdot 10^5$$$) — количество стогов сена.

В $$$i$$$-й из следующих $$$n$$$ строк содержится по два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1\le a_i, b_i\le 10^9$$$) — начальное количество тюков сена в $$$i$$$-м стоге сена и предел высоты, который ему присваивается после того, как он опустошается в первый раз.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество ходов, необходимое для обеспечения того, чтобы каждый стог сена был опустошен хотя бы один раз. Если невозможно опустошить каждый стог сена хотя бы один раз, выведите -1.

Пример
Входные данные
7
2
3 5
2 4
2
10 1
1 10
3
1 3
4 3
1 1
3
5 4
2 4
1 10
6
2 1
3 3
5 4
1 5
1 6
1 8
5
3 2
1 2
1 1
1 3
6 5
2
5 10
7 12
Выходные данные
8
-1
8
9
14
15
19
Примечание

В первом наборе входных данных мы можем выполнить следующую последовательность действий:

  • Переместите $$$3$$$ тюка из стога $$$1$$$ в стог $$$2$$$. Стог $$$1$$$ теперь пуст, и ему присвоено ограничение по высоте, равное $$$5$$$.
  • Переместите $$$5$$$ тюков из стога $$$2$$$ в стог $$$1$$$. Стог $$$2$$$ теперь пуст, и ему присвоено ограничение по высоте, равное $$$4$$$.

Приведенная выше последовательность требует $$$3 + 5 = 8$$$ ходов. Невозможно использовать менее $$$8$$$ ходов, так как следующая последовательность ходов недопустима:

  • Переместите $$$2$$$ тюка из стога $$$2$$$ в стог $$$1$$$. Стог $$$2$$$ теперь пуст, и ему присвоено ограничение по высоте, равное $$$4$$$.
  • Переместите $$$4$$$ тюка из стога $$$1$$$ в стог $$$2$$$. В стоге $$$1$$$ теперь $$$1$$$ тюк, в то время как в стоге $$$2$$$ находится $$$4$$$ тюка.
  • Стог $$$1$$$ нельзя очистить, так как высота стога $$$2$$$ уже равна $$$4$$$, поэтому больше нельзя перемещать тюки из стога $$$1$$$ в стог $$$2$$$.

Во втором наборе входных данных задача невыполнима. Это связано с тем, что ограничения по высоте обоих стогов слишком малы, и как только один из стогов опустошается, другой стог не может стать пустым из-за небольших ограничений по высоте.

В третьем наборе входных данных можно показать, что следующая последовательность ходов является оптимальной:

  • Переместите $$$1$$$ тюк из стога $$$1$$$ в стог $$$3$$$. Стог $$$1$$$ теперь пуст, и ему присвоено ограничение по высоте, равное $$$3$$$.
  • Переместите $$$3$$$ тюка из стога $$$2$$$ в стог $$$1$$$.
  • Переместите $$$1$$$ тюк из стога $$$2$$$ в стог $$$3$$$. Стог $$$2$$$ теперь пуст, и ему присвоено ограничение по высоте, равное $$$3$$$.
  • Переместите $$$3$$$ тюка из стога $$$3$$$ в стог $$$2$$$. Стог $$$3$$$ теперь пуст, и ему присвоено ограничение по высоте, равное $$$1$$$.

Приведенная выше последовательность требует $$$1 + 3 + 1 + 3 = 8$$$ ходов.