Type: Default 1000ms 256MiB

以太编辑

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

银狼既然是骇客,为什么不直接tp过去呢?

银狼正在执行一次网络渗透任务。她从网络表层出发,需要沿深度方向依次通过 $n$ 个漏洞注入点,抵达核心数据库。网络表层的深度为 $0$。

每深入一层消耗 $1$ 点以太能量。第 $i$ 个注入点位于深度 $x_i$ 处,经过时银狼可以发动以太编辑,恢复 $a_i$ 点能量。若以太能量低于 $0$ 及以下,那么银狼的任务就失败了。

请你计算最小的初始以太能量 $X$,使得她顺利完成任务,依次经过所有注入点。

Input Format

第一行一个整数 $T$($1 \le T \le 1000$),表示测试数据组数。保证 $\sum n \le 2 \times 10^5$。

每组数据:第一行一个整数 $n$($1 \le n \le 2 \times 10^5$),表示注入点数量。接下来 $n$ 行,每行两个整数 $x_i, a_i$($1 \le x_i, a_i \le 10^{12}$),表示第 $i$ 个注入点的深度和可恢复能量。保证 $x_i$ 严格递增。

Output Format

对于每组数据,输出一行一个整数,表示最小的初始以太能量 $X$。

2
3
2 3
5 1
7 2
1
10 5
3
10

Hint

第一组数据:初始能量 $X = 3$。走到深度 $2$ 时剩余 $1$,注入恢复 $3$ 后变为 $4$;走到深度 $5$ 时剩余 $2$,注入恢复 $1$ 后变为 $3$;走到深度 $7$ 时剩余 $1$,注入恢复 $2$ 后变为 $3$。全程能量未耗尽。可证 $X < 3$ 无法通过。

第二组数据:仅一个注入点,需要至少 $10$ 点能量走到深度 $10$。