404988: GYM101726 K Production in Yekaterinburg

Yekaterinburg is a Russian city located in the border between Europe and Asia, in the Ural Mountains. It's the fourth largest city in Russia, with more than 1.4 million residents. Its main economical activity is related to the production of industrial machines. The city's factories produce a large part of the machines used in Russia, and they are exported to several countries. In fact, the production of industrial tools is famous in the country. The tools are build by highly specialized machines and, for each tool to be produced the machines take some pre-determined time to produce it.

One of the factories has only one of those machines and its manager need your help to increase productivity. The tool orders arrive in the factory along the day, that is, they are not necessarily known at the beginning of the day. The manager thinks the employees are not choosing a good order to process the orders, and wants to analyze orders from previous days. This way, he asks you to determine, for a given day, the minimum instant at which all orders can be processed and finalized.

On the first line, a single integer T, the number of test cases.

Each test case has a single integer N on the first line, the number of orders to process in that day. The i-th of the next N lines has two integers s_i and d_i, the time at which the i-th order is available and the time it takes to process it, respectively.

Limits

• 1 ≤ N ≤ 10⁵
• The sum of N over all test cases won't exceed 5·10⁵
• 1 ≤ s_i, d_i ≤ 10⁴

For each test case, print the minimum instant at which all orders can be processed and finalized.

2
5
10 2
6 1
4 3
1 2
1 4
4
1 1
1 3
5 2
5 3

13
10