题目描述

Jack 在马路上（可以看成一条直线）上从左往右走，路上有 \(n\) 块石头，Jack 可以把第 \(i\) 块石头向右扔出 \(a_i\) 的距离。假设 Jack 从坐标 \(0\) 出发，当他遇到第奇数块石头时，他会捡起它并将其往右扔，而遇到第偶数个石头时不进行处理。当有两个石头在同一位置时，则先处理“射程”近（能扔的距离最短）的石头，然后 Jack 一直往右走，直到右方已经没有任何石头时，这时候计算 Jack 与出发点的距离。注意：Jack 在向右走的时候，会碰到他之前扔过的石头。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示数据组数；每组数据中，第一行为正整数 \(n(≤ 10^5)\)，表示石头数；接下来 \(n\) 行，每行有两个数字 \(p_i(≤10^5)\) 和 \(d_i(≤10^3)\)，分别表示第 \(i\) 块石头的坐标和射程，输入数据无序。

输出格式

对于每组数据，输出最后 Jack 与出发点的距离。

样例1

输入样例1

2
2
1 5
2 4
2
1 5
6 6

输出样例1

11
12

样例解释

样例 \(1.1\) 中，Jack 在坐标 \(1\) 处遇到第一块石头，向前扔了 \(5\) 个单位后，坐标变成 \(6\)；继续往前走,在坐标 \(2\) 处遇到第二块石头，忽略；然后继续往前走，在坐标 \(6\) 处又遇到了原来的第一块石头(现在是第三块石头),向前扔了 \(5\) 个单位后， 坐标变成 \(11\)；然后继续往前走，在坐标 \(11\) 时遇到的是第四块石头，忽略。前面已经没有石头了，因此此时离坐标原点的距离为 \(11\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T4\)

文件IO

freopen("stones.in","r",stdin);
freopen("stones.out","w",stdout);