P12805 [AMPPZ 2019] Frogs

Source: [AMPPZ 2019](https://amppz.tcs.uj.edu.pl/2019/data.html).

你可能会认为[青蛙](https://www.luogu.com.cn/user/3296)只擅长跳跃和鸣叫，但事实证明它们也相当精通编程！你的任务是选择三只青蛙组成参加 OpenFrogCup 的最佳团队。 在青蛙最喜欢的池塘中，有 $n$ 块石头排成一行，彼此间隔 1 米。每块石头上坐着一只青蛙。石头（和青蛙）从左到右编号为 $1, 2, \ldots, n$。第 $i$ 只青蛙坐在第 $i$ 块石头上，并由两个参数描述：其跳跃范围 $r_i$ 和编程能力 $s_i$。这只青蛙可以到达任何距离不超过 $r_i$ 米的石头（即索引 $j$ 在 $[i - r_i, i + r_i]$ 区间内的任何石头）。每只青蛙最多愿意跳跃一次。 参加 OpenFrogCup 的团队必须恰好由三名成员组成，且成员需能共同训练。这意味着必须存在一块所有三只青蛙都能跳到的石头（允许零距离跳跃）。请确定此类团队可能达到的最大编程能力总和。 问题的限制条件保证至少存在一个可能的三蛙团队。

**本题单个测试点内有多组测试数据。** 输入的第一行包含测试数据组数 $z$（$1 \leq z \leq 30$）。测试数据组按如下格式给出： 每组测试数据的第一行包含一个整数 $n$（$3 \leq n \leq 200\,000$）——石头数量（也即青蛙数量）。接下来的 $n$ 行每行包含两个整数 $r_i, s_i$（$1 \leq r_i, s_i \leq 200\,000$）——分别表示第 $i$ 只青蛙的跳跃范围和编程能力。 所有测试数据的 $n$ 值总和不超过 $500\,000$。

对于每组测试数据，输出一个整数——可能达到的最大编程能力总和。