DAS Queue
In recent years, electronic queue systems have become a staple in everyday life. Many government offices now feature a terminal that prints a ticket with a number, allowing visitors to check an electronic display to see how much longer they have to wait, eliminating the need to ask, "Who's last?"
However, these systems are not without flaws. The typical "first come, first served" approach can be problematic. In developing the innovative DAS "Queue" system, the goal was to move away from this principle. Instead, the system aims to minimize the negativity directed at the official whom people are waiting to see.
Each person in line has an irritability factor. If this factor is w, then after waiting t hours, the person will direct wt units of frustration and complaints at the official. For instance, if a visitor is served immediately upon arrival, the official experiences no negativity. However, if a visitor arrives at the start of the third hour and is served at the start of the fifth hour, the negativity amounts to 2w.
Each visitor requires exactly one hour of service, and they all arrive at the start of an hour. Your task is to determine the optimal order of serving the visitors, given their irritability factors and arrival times, to minimize the total negativity the official receives.
Input
The first line contains a single integer t — the number of cases to process. Each case description follows.
Each case begins with a number n on the first line — the number of visitors, followed by n lines each containing two integers r_i and w_i (1 ≤ r_i, w_i ≤ 10^6) — the hour the visitor arrives and their irritability factor, respectively.
The total number of visitors across all cases in a single test does not exceed 10^5.
Output
For each case, output a separate line with the minimum total negativity the official will receive.