Installations

In the morning, a service engineer at a telecom company receives a list of jobs to carry out that day: installing telephones, internet, IPTV, and repairing existing facilities. Each job comes with a deadline by which the client wants it finished, but because of the workload the engineer cannot always meet every deadline.

The engineer works on one job at a time. Every job $J_i$ has a serving time $s_i$ and a deadline $d_i$. Starting from time $0$, the jobs are carried out one after another in some order, and each job runs to completion once it starts. If $J_i$ finishes at time $C_i$, its penalty is $\max(0, C_i - d_i)$, that is, how far it runs past its deadline. All values are positive integers with $0 < s_i \le d_i$.

Arrange the jobs so that the sum of the two largest penalties is as small as possible.

For example, take six jobs whose $(s_i, d_i)$ are $(1, 7), (4, 7), (2, 4), (2, 15), (3, 5), (3, 8)$ for $i = 1, \dots, 6$. Figure 1 shows a schedule that minimizes the sum of the two largest penalties. Here the two largest penalties belong to $J_2$ and $J_6$, equal to $6$ and $1$, so their sum is $7$.

The first line contains the number of test cases $T$.

Each test case begins with a line containing an integer $n$ ($1 \le n \le 500$), the number of jobs. Each of the next $n$ lines contains two integers $s_i$ and $d_i$ ($1 \le s_i \le d_i \le 10000$): the serving time and the deadline of job $J_i$.

For each test case, print a single line with the sum of the two largest penalties over an optimal schedule.