A16615 · Haystacks · GESP考级

题目描述

在下一个新月之夜，宇宙将会重置，从佛罗里达开始。现在轮到“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 \time 10^5$），表示干草堆的数量。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 10^9$），分别表示第 $i$ 个干草堆初始的干草捆数量，以及该堆第一次被清空后分配的高度上限。 保证所有测试用例中 $n$ 的总和不超过 $5 \times 10^5$。

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

输入 #1

输出 #1