D. 书架上的古籍

题目描述

在古老的"星辰图书馆"中，有 $n$ 个编号分别为从 $1$ 至 $n$ 的书架。书架 $i$ 最初存放着 $a_i$ 本古籍。一本失传的《星穹秘典》藏在某个书架底部，但具体位置未知。你的任务是移动古籍，确保每个书架都被彻底清空检查一次。

移动古籍的规则特殊：

• 当书架 $i$ 首次被清空时，会触发机关，使其承重梁变得脆弱，此后最多只能容纳 $b_i$ 本书。
• 每次操作：选择两个书架 $i$ 和 $j$。若 $i$ 未被清空过，或 $i$ 当前书籍数严格小于 $b_i$，则可将 $1$ 本书从 $j$ 移到 $i$。

关键限制：书架在首次清空前无承重限制，可接受任意数量书籍；首次清空后，书籍数不可超过 $b_i$。

求使得所有书架均被清空至少一次的最小操作次数。若不可能实现，输出 $-1$。

输入格式

第一行一个整数 $t$，表示给定 $t$ 组测试用例。

对于每一组测试用例，第一行包含有一个正整数 $n$，表示书架数量 $n$。接下来 $n$ 行数据，每行两个整数 $a_i$, $b_i$ ($1 \le i \le n$)，含义如上。

输出格式

对于每一组测试样例，输出一行一个整数，表示使得所有书架均被清空至少一次的最小操作次数。若不可能实现，输出 $-1$。

样例输入1

2
2
3 5
2 4
2
10 1
1 10

样例输出1

8
-1

数据范围

• 对于 $10\%$ 的数据，$2 \le \sum n \le 20$, $1 \le a_i, b_i \le 10^9$。
• 对于 $30\%$ 的数据，$2 \le \sum n \le 10^3$, $1 \le a_i, b_i \le 10^9$。
• 对于 $100\%$ 的数据，$2 \le n \le 5 \times 10^5$, $1 \le a_i, b_i \le 10^9$。