Shopping Mall
InterviewTime limit1sMemory limit512 MB
Simulate customers choosing the counter with the minimum total wait (lowest index on ties), then compute a weighted sum of membership numbers in the order customers leave.
- Level
Hard8 of 10
- Topics
- Simulation, Heap, Greedy, Sorting
- Solved
- No attempts yet
Problem
N customers who have finished shopping at a large shopping mall are standing in line in front of the checkout counters, waiting to pay and leave. Each customer takes a large cart of goods to a counter. The mall has K counters arranged side by side, as shown in the figure below.
A guide directs each customer to the counter where they can finish paying the soonest. The guide already knows how long the people waiting at each counter will take to pay. If two counters have the same waiting time, the guide directs the customer to the counter with the smallest number. For example, if counters 3 and 5 both have a minimum waiting time of 15 minutes, the guide sends the customer to counter 3.
A customer who finishes paying leaves the mall completely through the exit. If several customers finish paying at the same time, the one at the higher-numbered counter, which is closer to the exit, leaves first. For example, if two customers finish at counters 4 and 10 at the same time, the customer at counter 10, the higher-numbered counter, leaves the mall first. Paying for goods takes 1 minute regardless of the type of goods. That is, a customer with w goods takes exactly w minutes to finish paying.
Given the information (membership number, number of goods purchased) of the N customers standing in line to enter the counters, you must determine the order in which they pay and leave the mall. Assume that no time is needed to enter a counter or to leave a counter.
Input
The first line of the input gives two integers N (1 ≤ N ≤ 100,000) and k (1 ≤ k ≤ 100,000). The next N lines give the information of the N customers in order from the front of the line to the back. The i-th line consists of the membership number idi (1 ≤ idi ≤ 1,000,000) of the i-th customer from the front of the line and the number wi (1 ≤ wi ≤ 20) of goods they purchased. All N membership numbers are distinct.
Output
Let r1, r2, ..., rN be the membership numbers of the N customers in the order they leave the mall. Output the value of 1×r1 + 2×r2 + ... + N×rN. Note that the output value can exceed the range of int.