你可能认为青蛙只会跳跃和鸣叫，但事实证明它们也是非常精通编程的程序员！你的任务是为 OpenFrogCup 选择三只青蛙组成最佳团队。

在青蛙最喜欢的池塘里，有 $n$ 块石头排成一排，每块石头相距 1 米。每块石头上都坐着一只青蛙。石头（以及青蛙）从左到右编号为 $1, 2, \dots, n$。第 $i$ 只青蛙坐在第 $i$ 块石头上，由两个参数描述：它的跳跃范围 $r_i$ 和编程技能 $s_i$。这只青蛙可以到达任何距离不超过 $r_i$ 米的石头（换句话说，任何索引 $j$ 在 $[i - r_i, i + r_i]$ 范围内的石头）。每只青蛙最多愿意跳跃一次。

OpenFrogCup 的团队必须由恰好三名成员组成，且它们可以一起训练。这意味着必须存在一块石头，这三只青蛙都能跳到上面（允许零距离跳跃）。确定这样一支团队的编程技能之和的最大值。

题目限制保证至少存在一支可行的三人青蛙团队。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 30$)。接下来是各个测试用例，每个测试用例的格式如下：

测试用例的第一行包含一个整数 $n$ ($3 \le n \le 200\,000$)，表示石头的数量（也是青蛙的数量）。 接下来的 $n$ 行，每行包含两个整数 $r_i, s_i$ ($1 \le r_i, s_i \le 200\,000$)，分别表示第 $i$ 只青蛙的跳跃范围和编程技能。

所有测试用例的 $n$ 之和不超过 $500\,000$。

输出格式

对于每个测试用例，输出一个整数，表示三人团队技能之和的最大值。

样例

样例输入 1

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

样例输出 1

62
60
11