题目背景

Source: AMPPZ 2019.

题目描述

你可能会认为青蛙只擅长跳跃和鸣叫，但事实证明它们也相当精通编程！你的任务是选择三只青蛙组成参加 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$。

输出格式

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

3
4
1 39
2 17
4 5
1 40
3
1 10
1 20
1 30
7
5 4
4 3
3 2
2 1
3 2
4 3
5 4

62
60
11