A single printer serves several departments. Department i has submitted a queue queues[i] of jobs, and each job is a pair (d, w): it takes d minutes to print and its urgency is w. Jobs of one department must be printed in the order given, but the printer may interleave jobs from different departments in any way it likes. Printing starts at minute 0, one job at a time, with no pauses between jobs.
If a job finishes at minute t, it costs w * t. Return the minimum possible total cost of printing every job.
Examples
Input: queues = [[(3, 1), (1, 1)], [(2, 4)]]
Output: 19
Explanation: print (2, 4) first (finishes at 2, cost 8), then (3, 1) (finishes
at 5, cost 5), then (1, 1) (finishes at 6, cost 6).
Input: queues = [[(2, 3), (4, 2)], [(1, 1), (5, 5)], [(3, 0)]]
Output: 73
Constraints
0 <= len(queues) <= 1000; a queue may be empty- At most
2 * 10**4jobs in total 1 <= d <= 10**9,0 <= w <= 10**9- The answer is exact and can be far larger than
2**63.
Goals
- Use an exchange argument to compare two adjacent groups of jobs
- Group jobs inside a queue whose order is fixed before comparing across queues
- Compare ratios exactly with integer cross-multiplication