在下一个新月,宇宙将从佛罗里达州开始重置。佛罗里达人有责任阻止这一切,但他首先需要找到一件重要的物品。
有 $$$n$$$ 干草堆,标记为从 $$$1$$$ 到 $$$n$$$,其中干草堆 $$$i$$$ 包含 $$$a_i$$$ 干草堆。其中一个干草堆下面藏着一根针,但你不知道是哪一根。你的任务是移动干草堆,使每个干草堆至少清空一次,这样你就可以检查针是否隐藏在特定的干草堆下面。
然而,过程并不那么简单。一旦干草堆 $$$i$$$ 第一次被清空,它将被指定高度限制,并且不能再容纳超过 $$$b_i$$$ 干草堆。更正式地说,移动描述如下:
- 选择两个干草堆 $$$i$$$ 和 $$$j$$$。如果 haystack $$$i$$$ 之前没有被清空,或者 haystack $$$i$$$ 包含严格小于 $$$b_i$$$ 的干草堆,则您可以将 $$$1$$$ 干草堆从 haystack $$$j$$$ 移动到 haystack $$$i$$$。
注意:在清空干草堆之前,它没有高度限制,并且您可以将任意数量的干草堆移到该干草堆上。
计算确保每个干草堆至少清空一次所需的最小移动次数,或者报告这是不可能的。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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
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
输出 #1
8 -1 8 9 14 15 19
注意
在第一个测试用例中,我们可以执行以下移动序列:
- 将 $$$3$$$ 干草堆从干草堆 $$$1$$$ 移至干草堆 $$$2$$$。 Haystack $$$1$$$ 现已清空,并指定高度限制为 $$$5$$$。
- 将 $$$5$$$ 干草堆从干草堆 $$$2$$$ 移至干草堆 $$$1$$$。 Haystack $$$2$$$ 现已清空,并指定高度限制为 $$$4$$$。
上述序列需要 $$$3 + 5 = 8$$$ 步。不可能使用少于 $$$8$$$ 的移动,因为以下移动顺序无效:
- 将 $$$2$$$ 干草堆从干草堆 $$$2$$$ 移至干草堆 $$$1$$$。 Haystack $$$2$$$ 现已清空,并指定高度限制为 $$$4$$$。
- 将 $$$4$$$ 干草堆从干草堆 $$$1$$$ 移至干草堆 $$$2$$$。干草堆 $$$1$$$ 现在有 $$$1$$$ 干草堆,而干草堆 $$$2$$$ 有 $$$4$$$ 干草堆。
- 干草堆 $$$1$$$ 无法清空,因为干草堆 $$$2$$$ 已经达到 $$$4$$$ 的高度限制,因此无法再将干草堆从干草堆 $$$1$$$ 移至干草堆 $$$2$$$。
在第二个测试用例中,该任务是不可能的。这是因为两个干草堆的高度限制都太小,一旦其中一个干草堆被清空,另一个干草堆就会因为高度限制太小而无法清空。
在第三个测试用例中,以下移动顺序可以被证明是最佳的:
- 将 $$$1$$$ 干草堆从干草堆 $$$1$$$ 移至干草堆 $$$3$$$。 Haystack $$$1$$$ 现已清空,并指定高度限制为 $$$3$$$。
- 将 $$$3$$$ 干草堆从干草堆 $$$2$$$ 移至干草堆 $$$1$$$。
- 将 $$$1$$$ 干草堆从干草堆 $$$2$$$ 移至干草堆 $$$3$$$。 Haystack $$$2$$$ 现已清空,并指定高度限制为 $$$3$$$。
- 将 $$$3$$$ 干草堆从干草堆 $$$3$$$ 移至干草堆 $$$2$$$。 Haystack $$$3$$$ 现已清空,并指定高度限制为 $$$1$$$。
上述序列需要 $$$1 + 3 + 1 + 3 = 8$$$ 步。