题目描述

小黄来到了他一直梦寐以求的巧克力工厂，这里有各种各样的巧克力等待品尝。工厂里只有一台巧克力加工机，所有巧克力必须加工完成后才能食用。 巧克力并非一开始就全部加工好，而是会在一天中的不同时间陆续加工完成。不同的巧克力，小黄吃完它所需要的时间也不同。只会吃的小黄完全不懂算法，你能帮他想想办法，让他尽早吃完所有巧克力吗？

输入格式

第一行：一个整数 $T$，表示测试用例数量

每组测试用例：

• 第一行：一个整数 $N$，表示巧克力数量。
• 接下来 $N$ 行：每行两个整数 $s_i,d_i$：
  • $s_i$：第 $i$ 块巧克力的加工完成时间（该时刻及之后才能品尝）。
  • $d_i$：吃完第 $i$ 块巧克力所需的时间。

保证 $1 \leq T \leq 100，1 \leq N \leq 10^5$，所有测试用例的 $N$ 之和不超过 $5\times 10^5$，$1 \leq s_i, d_i \leq 10^9$。

输出格式

对于每组测试用例，输出一行一个整数，表示小黄吃完所有巧克力的最早时刻。

1
3
1 2
3 1
1 1

5