TIME TO END THIS! – You've reached the very heart of the Void and found the last bastion of the enemy's power. It's time to end the tale of the Orb of Dominance and put a stop to this chaos. —— Minecraft Dungeons: Broken Citadel

题目背景

拯救虚空之后，你来到了末地外岛，这里有一片密集的城市群，虽然已经支离破碎，但或许仍有值得探索之物藏在其中，千万小心！

题目描述

城市群由 n 个城堡组成，不同部分之间需要依靠鞘翅（滑翔翼）飞行前往。

你计划进行一次鞘翅飞行旅行，探索 n 个城堡。请规划一条路线，从某一座大楼出发，按照任意顺序不重不漏地探索其他所有城堡，最终返回到起始城堡。

第 i 座城堡自身高度为 h_i，城堡顶部设有一段能够竖直向上攀爬的瞭望台，其高度为 c_i。

任意城堡 i 可以前往城堡 j，遵循如下的移动规则：

1. 爬上当前所在城堡 i 顶部的瞭望台，到达高度 h_i + c_i。
2. 使用鞘翅从当前高度 h_i + c_i 飞向城堡 j 的顶部，目标高度为 h_j；向高处飞行消耗烟花火箭（助推器），具体地：
   • 若 h_j \leq h_i + c_i, 即从高处飞往低处，不消耗烟花火箭。
   • 若 h_j \geq h_i + c_i, 即从低处飞往高处，则消耗的烟花火箭量等于目标高度与起飞高度之差，即 h_j - (h_i + c_i)。
   • 即，从城堡 i 前往城堡 j 所消耗的烟花火箭量为：\max(0, h_j - (h_i + c_i))。

你的任务是计算出完成这次旅行（访问所有大楼恰好一次并返回起点）所需的最小烟花火箭消耗总量。

每个测试文件由多个测试用例组成。第一行包含一个整数 t (1 \leq t \leq 10^4) 表示测试用例数。

对于每个测试用例，第一行读入一个整数 n (2 \leq n \leq 2 \times 10^5)，表示城堡的数量。

接下来 n 行，每行读入两个非负整数 h_i,c_i (0 \leq h_i,c_i \leq 10^9)，分别表示第 i 座城堡的高度及其瞭望台的高度。

数据保证所有测试用例 n 的总和不超过 2 \times 10^5。

对于每组测试数据，输出一行一个非负整数，表示完成旅行的最小总烟花火箭消耗量。

这一段的纸质版题面有误，将往返的火箭消耗写反，请以电子版为准 在测试用例 1 中，一种最优的旅行方式是从城堡 1 前往城堡 2，再从城堡 2 回到城堡 1。1→2 不消耗烟花火箭，2→1 的烟花火箭消耗是 8，烟花火箭消耗总量是 8。

在测试用例 2 中，一种最优的旅行方式是 5→2→3→6→4→1→5。每次移动的烟花火箭消耗分别是 0,0,0,1,0,1，烟花火箭消耗总量是 2。