Haystacks
Contest: Codeforces Round 996 (Div. 2)
Difficulty rating: 2800
Tags: brute force, constructive algorithms, data structures, greedy, sortings

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
8
-1
8
9
14
15
19

Editorial:
Let's say we fixed some permutation $$$\sigma$$$ of $$$1, \dots, n$$$ such that we empty haystacks in the order $$$\sigma_1, \dots, \sigma_n$$$. Notice that a choice of $$$\sigma$$$ is possible if and only if the final stack $$$\sigma_n$$$ can be cleared, which is equivalent to the constraint $$$$$$a_{\sigma_1} + \dots + a_{\sigma_n} \leq b_{\sigma_1} + \dots + b_{\sigma_{n-1}}.$$$$$$ With this added constraint, the optimal sequence of moves is as follows:
• Iterate $$$i$$$ through $$$1, \dots, n-1$$$. For each $$$i$$$, try to move its haybales to haystacks $$$1, \dots, i-1$$$, and if they are all full then move haybales to haystack $$$n$$$. Once this process terminates, move all haystacks from $$$n$$$ back onto arbitrary haystacks $$$1, \dots, n-1$$$, being careful to not overflow the height limits.
Consider adjacent pairs $$$(a_i, b_i) <_{\sigma} (a_j, b_j)$$$. Then, if the choice of $$$\sigma$$$ is optimal, it must not be better to swap their ordering, i.e. $$$$$$\begin{align*} \overbrace{(a_i, b_i) <_{\sigma} (a_j, b_j)}^{\text{optimal}} \implies& \max(a_i, a_i + a_j - b_i) \leq \max(a_j, a_i + a_j - b_j) \\ \iff& \max(-a_j, -b_i) \leq \max(-a_i, -b_j)\\ \iff& \min(a_j, b_i) \geq \min(a_i, b_j). \end{align*}$$$$$$ As a corollary, there exists an optimal $$$\sigma$$$ satisfying the following properties:
Claim [Optimality conditions of $$$\sigma$$$].
• All pairs with $$$a_i < b_i$$$ come first. Then, all pairs with $$$a_i = b_i$$$ come next. Then, all pairs with $$$a_i > b_i$$$.
• The pairs with $$$a_i < b_i$$$ are in ascending order of $$$a_i$$$.
• The pairs with $$$a_i > b_i$$$ are in descending order of $$$b_i$$$.
Now, we add in the constraint on the final term $$$\sigma_n$$$ of the ordering. We will perform casework on this final haystack. Notice that for any fixed $$$a_n, b_n$$$, if $$$$$$\max_{1 \leq i \leq n-1} \left\{\sum_{j=1}^i a_{\sigma_j} - \sum_{j=1}^{i-1} b_{\sigma_j}\right\}$$$$$$ is maximized, then so is $$$$$$\max_{1 \leq i \leq n} \left\{\sum_{j=1}^i a_{\sigma_j} - \sum_{j=1}^{i-1} b_{\sigma_j}\right\}.$$$$$$ So, if we were to fix any last haystack $$$\sigma_n$$$, the optimality conditions tell us that we should still order the remaining $$$n-1$$$ haystacks as before. Now, we may iterate over all valid $$$\sigma_n$$$ and compute the answer efficiently as follows: maintain a segment tree with leaves representing pairs $$$(a_i, b_i)$$$ and range queries for $$$\max_{1 \leq i \leq n} \left\{\sum_{j=1}^i a_{\sigma_j} - \sum_{j=1}^{i-1} b_{\sigma_j}\right\}$$$. This gives an $$$O(n \log n)$$$ solution.
Note that it is possible to implement this final step using prefix and suffix sums to yield an $$$O(n)$$$ solution, but it is not necessary to do so.