CF2055E Haystacks

在下一个新月之夜，宇宙将会重置，从佛罗里达开始。现在轮到“Florida Man”来阻止这一切，但他首先需要找到一个重要的物品。有 $n$ 个干草堆，编号从 $1$ 到 $n$，其中第 $i$ 个干草堆包含 $a_i$ 个干草捆。某一个干草堆下藏着一根针，但你并不知道是哪一个。你的任务是移动干草捆，使得每个干草堆至少被清空一次，这样你才能检查该干草堆下是否藏着针。 然而，过程并不简单。一旦某个干草堆 $i$ 第一次被清空，它将被分配一个高度上限，此后该干草堆中不能再有超过 $b_i$ 个干草捆。更正式地说，每次操作如下： - 选择两个干草堆 $i$ 和 $j$。如果干草堆 $i$ 还没有被清空过，或者干草堆 $i$ 当前的干草捆数量严格小于 $b_i$，你可以从干草堆 $j$ 向干草堆 $i$ 移动恰好 $1$ 个干草捆。 注意：在干草堆被清空之前，没有高度上限，你可以向该干草堆移动任意数量的干草捆。 请计算最少需要多少次操作，才能保证每个干草堆至少被清空一次。如果无法做到，请输出 $-1$。

每个测试点包含多个测试用例。第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数，表示最少需要的操作次数，才能保证每个干草堆至少被清空一次。如果无法做到，输出 $-1$。

在第一个测试用例中，可以按如下顺序操作： - 从干草堆 $1$ 向干草堆 $2$ 移动 $3$ 个干草捆。此时干草堆 $1$ 被清空，并被分配高度上限 $5$。 - 从干草堆 $2$ 向干草堆 $1$ 移动 $5$ 个干草捆。此时干草堆 $2$ 被清空，并被分配高度上限 $4$。 上述操作共需要 $3 + 5 = 8$ 次。无法用更少的操作完成，因为如下操作是无效的： - 从干草堆 $2$ 向干草堆 $1$ 移动 $2$ 个干草捆。此时干草堆 $2$ 被清空，并被分配高度上限 $4$。 - 从干草堆 $1$ 向干草堆 $2$ 移动 $4$ 个干草捆。此时干草堆 $1$ 还剩 $1$ 个干草捆，干草堆 $2$ 有 $4$ 个干草捆。 - 此时干草堆 $1$ 无法被清空，因为干草堆 $2$ 已经达到了高度上限 $4$，无法再从干草堆 $1$ 向干草堆 $2$ 移动干草捆。 在第二个测试用例中，任务无法完成。因为两个干草堆的高度上限都太小，一旦其中一个被清空，另一个就无法被清空。 在第三个测试用例中，最优的操作顺序如下： - 从干草堆 $1$ 向干草堆 $3$ 移动 $1$ 个干草捆。此时干草堆 $1$ 被清空，并被分配高度上限 $3$。 - 从干草堆 $2$ 向干草堆 $1$ 移动 $3$ 个干草捆。 - 从干草堆 $2$ 向干草堆 $3$ 移动 $1$ 个干草捆。此时干草堆 $2$ 被清空，并被分配高度上限 $3$。 - 从干草堆 $3$ 向干草堆 $2$ 移动 $3$ 个干草捆。此时干草堆 $3$ 被清空，并被分配高度上限 $1$。 上述操作共需要 $1 + 3 + 1 + 3 = 8$ 次。 由 ChatGPT 4.1 翻译