题目描述

徐老师终于站在了那座令人生畏的恶魔塔顶端，他的心中充满了胜利的喜悦与紧张交织的情感。在他面前，美丽的蛋蛋公主正静静地等待着心目中王子的到来，她那双清澈如水的眼眸中闪烁着希望的光芒。徐老师毫不犹豫地牵起公主的手，两人并肩奔跑在一条黑暗的长廊上，周围是阴森恐怖的氛围，墙壁上偶尔闪过的幽光让人不寒而栗。然而，徐老师和蛋蛋公主却仿佛被一股强大的信念所驱动，他们的脚步坚定而有力，每一次落地都伴随着回响，在这寂静的黑暗中显得格外响亮。长廊似乎无穷无尽，他们知道，只要坚持下去，就一定能够逃离这个邪恶的世界，迎接属于他们的光明未来。长廊可以视为一条数轴。在长廊上有 $n$​ 个火把，从左往右依次编 号为$1$​ 到 $n$​，第$i$​个火把坐标为$x_i$​，可以照亮数轴上的部分$[x_i-r_i,x_i+r_i]$​（包含两边界)。如果一 个位置没有被任何火把照亮，那么怕黑的蛋蛋公主是不敢去那里的。

徐老师和蛋蛋公主可以在长廊上往左或者往右走。如果他的位置与某个火把重合，他可以选择打开或者关闭这个火把。一开始， 徐老师的位置与第$1$ 个火把重合，第$1$ 个火把处于燃烧状态，其它所有火把都处于熄灭状态。徐老师希望在火光下走到第 $n$ 个火把的位置，并且使得第 $n$ 个火把处于燃烧状态，其它所有火把都处于熄灭状态。

请写一个程序，帮助徐老师和蛋蛋公主找到路程最短的路线，或告诉徐老师逃不出恶魔塔。

输入格式

第一行包含一个正整数 $T$，表示测试数据的组数。 每组数据第一行包含一个正整数$n$，表示火把的数量。 接下来$n$行，每行两个正整数分别$x_i,r_i$表示每个火把的位置和火光半径。

输出格式

对于每组数据输出一行一个整数，即最短的总路程，若无解请输出"$-1$"。

4
5
1 5
3 1
4 9
7 8
8 4
2
1 1
10 10
2
1 10
10 8
2
1 1000000000
1000000000 999999999

21
-1
-1
2999999997

数据范围

• $30\%$的数据： $n ≤ 2$。
• 另$30\%$的数据：$n ≤ 1000, T ≤ 10$。
• 另$40\%$的数据：$n ≤ 100000$。
• 对于全部数据：$1 ≤ T ≤ 2000, \Sigma n ≤ 300000, n ≥ 2 , 1 ≤ x_1 < x_2 < x_3 < ...< x_n ≤ 10^9 , 1 ≤ r_i ≤ 10^9 $。
• 提示：最优解一定是从 $1$一路往右点亮火把走到$n$，再回到 $1$，再一路往右熄灭火把走到 $n$ 。