Electronic Queue System
Time limit2sMemory limit256 MB
Given each visitor's arrival hour and irritability, serve everyone in one-hour slots to minimize total irritability times waiting time.
- Level
Medium7 of 10
- Topics
- Greedy, Sorting, Heap, Implementation
- Solved
- No attempts yet
Problem
Over the past few years, electronic queues have become firmly established in everyday life. In many government offices you can find a terminal that prints a slip with a number, and without asking the usual question "Who is last?", visitors learn from an electronic board how much longer they must wait and when their turn will come.
However, such systems are still far from perfect. For example, the standard principle of any queue, "first come, first served", raises questions. When developing the innovative electronic queue system, it was decided to make it so that this principle need not be observed. Instead, the new system is meant to minimize the amount of negativity that falls on the official receiving the people standing in line.
It is known that each person has a criterion called irritability. If this parameter equals w, then after t hours of waiting in the queue, this person will unleash exactly wt units of anger and abuse on the official. For instance, if a visitor is served immediately after arriving, the official suffers no harm, but if a visitor arrived at the start of the third hour and service began only at the start of the fifth, the amount of anger equals 2w.
It is also known that serving each visitor takes exactly one hour, and each visitor arrives at the start of some hour. Your task is, from the given irritability values and arrival times of the visitors, to determine how much negativity the official will receive under the optimal order of serving the clients.
Input
The first line contains a single integer t, the number of cases you must process. Then follow t descriptions of the cases themselves.
The description of each case consists of the number n on the first line, the number of visitors, and n descriptions of the visitors. For each visitor, a separate line contains two integers ri and wi (1 ≤ ri, wi ≤ 106), the number of the hour at whose start the visitor arrived and their irritability coefficient, respectively.
The total number of visitors across all cases of one test does not exceed 105.
Output
For each case, output on a separate line the answer: the minimum total amount of negativity that the official will receive.