CF2055E.Haystacks

On the next new moon, the universe will reset, beginning with Florida. It's up to Florida Man to stop it, but he first needs to find an important item.

There are $n$ haystacks labelled from $1$ to $n$, where haystack $i$ contains $a_i$ haybales. One of the haystacks has a needle hidden beneath it, but you do not know which one. Your task is to move the haybales so that each haystack is emptied at least once, allowing you to check if the needle is hidden under that particular haystack.

However, the process is not that simple. Once a haystack $i$ is emptied for the first time, it will be assigned a height limit and can no longer contain more than $b_i$ haybales. More formally, a move is described as follows:

• Choose two haystacks $i$ and $j$. If haystack $i$ has not been emptied before, or haystack $i$ contains strictly less than $b_i$ haybales, you may move exactly $1$ haybale from haystack $j$ to haystack $i$.

Note: Before a haystack is emptied, it has no height limit, and you can move as many haybales as you want onto that haystack.

Compute the minimum number of moves required to ensure that each haystack is emptied at least once, or report that it is impossible.

下一个新月之时，宇宙将重置，而重置将从佛罗里达州开始。阻止这一切的重任落在了“佛罗里达男”身上，但他首先需要找到一件重要物品。

共有 $n$ 个干草堆，编号从 $1$ 到 $n$，其中第 $i$ 个干草堆包含 $a_i$ 个干草捆。其中一个干草堆下方藏有一根针，但你并不知道是哪一个。你的任务是移动干草捆，使得每个干草堆至少被清空一次，从而得以检查该干草堆下方是否藏有那根针。

然而，这一过程并不简单。一旦干草堆 $i$ 首次被清空，它将被赋予一个高度限制，此后其内干草捆数量不得超过 $b_i$ 个。更准确地说，一次操作定义如下：

• 选择两个干草堆 $i$ 和 $j$。若干草堆 $i$ 尚未被清空过，或其当前干草捆数量严格小于 $b_i$，则你可以恰好将 $1$ 个干草捆从干草堆 $j$ 移动到干草堆 $i$。

注意：在某个干草堆首次被清空之前，它没有高度限制，因此你可以向其上任意多次移动干草捆（即数量不受限）。

请计算确保每个干草堆至少被清空一次所需的最少操作次数；若不可能实现，则报告为不可能。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le 5\cdot 10^5$) — the number of haystacks.

The $i$-th of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1\le a_i, b_i\le 10^9$) — the initial number of haybales in the $i$-th haystack, and the height limit that it is assigned after it is emptied for the first time.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2\le n\le 5\cdot 10^5$）—— 表示干草堆的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1\le a_i, b_i\le 10^9$）—— 分别表示第 $i$ 个干草堆的初始干草捆数量，以及该干草堆在首次被清空后所分配的高度限制。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

For each test case, print a single integer — the minimum number of moves required to ensure that each haystack is emptied at least once. If it is not possible to empty each haystack at least once, output -1.

对于每个测试用例，输出一个整数——确保每个干草堆至少被清空一次所需的最少移动次数。如果无法使每个干草堆至少被清空一次，则输出 $-1$。

In the first test case, we can do the following sequence of moves:

• Move $3$ haybales from haystack $1$ to haystack $2$. Haystack $1$ is now emptied, and is assigned a height limit of $5$.
• Move $5$ haybales from haystack $2$ to haystack $1$. Haystack $2$ is now emptied, and is assigned a height limit of $4$.

The above sequence requires $3 + 5 = 8$ moves. It is not possible to use less than $8$ moves as the following sequence of moves is invalid:

• Move $2$ haybales from haystack $2$ to haystack $1$. Haystack $2$ is now emptied, and is assigned a height limit of $4$.
• Move $4$ haybales from haystack $1$ to haystack $2$. Haystack $1$ now has $1$ haybale, while haystack $2$ has $4$ haybales.
• Haystack $1$ cannot be emptied as haystack $2$ is already at its height limit of $4$, so no more haybales can be moved from haystack $1$ to haystack $2$.

In the second test case, the task is impossible. This is because the height limits of both haystacks are too small that once one of the haystacks is emptied, the other haystack cannot be emptied due to the small height limits.

In the third test case, the following sequence of moves can be shown to be optimal:

• Move $1$ haybale from haystack $1$ to haystack $3$. Haystack $1$ is now emptied, and is assigned a height limit of $3$.
• Move $3$ haybales from haystack $2$ to haystack $1$.
• Move $1$ haybale from haystack $2$ to haystack $3$. Haystack $2$ is now emptied and is assigned a height limit of $3$.
• Move $3$ haybales from haystack $3$ to haystack $2$. Haystack $3$ is now emptied, and is assigned a height limit of $1$.

The above sequence requires $1 + 3 + 1 + 3 = 8$ moves.

在第一个测试用例中，我们可以执行以下移动序列：

• 将 $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$ 次移动。