8919번 - Installations 다국어채점 준비 중

In the morning, service engineers in a telecom company receive a list of jobs which they must serve today. They install telephones, internet, ipTVs, etc and repair troubles with established facilities. A client requires a deadline when the requested job must be completed. But the engineers may not complete some jobs within their deadlines because of job overload. For each job, we consider, as a penalty of the engineer, the difference between the deadline and the completion time. It measures how long the job proceeds after its deadline. The problem is to find a schedule minimizing the sum of the penalties of the jobs with the two largest penalties.

A service engineer gets a list of jobs J_i with a serving time s_i and a deadline d_i . A job J_i needs time s_i , and if it is completed at time C_i , then the penalty of J_i is defined to be max{0, C_i - d_i} . For convenience, we assume that the time t when a job can be served is 0 ≤ t < ∞ and s_i and d_i are given positive integers such that 0 < s_i ≤ d_i . The goal is to find a schedule of jobs minimizing the sum of the penalties of the jobs with the two largest penalties.

For example, there are six jobs J_i with the pair (s_i, d_i) of the serving time s_i and the deadline d_i , i =1,...,6 , where (s₁ , d₁) = (1, 7), (s₂ , d₂) = (4, 7), (s₃ , d₃) = (2, 4), (s₄ , d₄) = (2, 15), (s₅ , d₅) = (3, 5), (s₆ , d₆) = (3, 8). Then Figure 1 represents a schedule which minimizes the sum of the penalties of the jobs with the two largest penalties. The sum of the two largest penalties of an optimal schedule is that of the penalties of J₂ and J₆ , namely 6 and 1, respectively, which is equal to 7 in this example.

Figure 1. The optimal schedule of the example

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given on the first line of the input. The first line of each test case contains an integer n (1 ≤ n ≤ 500) , the number of the given jobs. In the next n lines of each test case, the i -th line contains two integer numbers s_i and d_i, representing the serving time and the deadline of the job J_i, respectively, where 1 ≤ s_i ≤ d_i ≤10,000 . 

Your program is to write to standard output. Print exactly one line for each test case. The line contains the sum of the penalties of the jobs with the two largest penalties.