CF1907D Jumping Through Segments

Polycarp is designing a level for a game. The level consists of $ n $ segments on the number line, where the $ i $ -th segment starts at the point with coordinate $ l_i $ and ends at the point with coordinate $ r_i $ . The player starts the level at the point with coordinate $ 0 $ . In one move, they can move to any point that is within a distance of no more than $ k $ . After their $ i $ -th move, the player must land within the $ i $ -th segment, that is, at a coordinate $ x $ such that $ l_i \le x \le r_i $ . This means: - After the first move, they must be inside the first segment (from $ l_1 $ to $ r_1 $ ); - After the second move, they must be inside the second segment (from $ l_2 $ to $ r_2 $ ); - ... - After the $ n $ -th move, they must be inside the $ n $ -th segment (from $ l_n $ to $ r_n $ ). The level is considered completed if the player reaches the $ n $ -th segment, following the rules described above. After some thought, Polycarp realized that it is impossible to complete the level with some values of $ k $ . Polycarp does not want the level to be too easy, so he asks you to determine the minimum integer $ k $ with which it is possible to complete the level.

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ )—the number of test cases. Descriptions of the test cases follow. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ )—the number of segments in the level. The following $ n $ lines. The $ i $ -th line contain two integers $ l_i $ and $ r_i $ ( $ 0 \le l_i \le r_i \le 10^9 $ )—the boundaries of the $ i $ -th segment. Segments may intersect. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output a single integer—the minimum value of $ k $ with which it is possible to complete the level.

In the third example, the player can make the following moves: - Move from point $ 0 $ to point $ 5 $ ( $ 3 \le 5 \le 8 $ ); - Move from point $ 5 $ to point $ 10 $ ( $ 10 \le 10 \le 18 $ ); - Move from point $ 10 $ to point $ 7 $ ( $ 6 \le 7 \le 11 $ ). Note that for the last move, the player could have chosen not to move and still complete the level.