50055. Waiting Time at Supermarket

I'm a slow walker, but I never walk backwards.

Task Description

Write a program to compute the total waiting time of customers in a supermarket when they check out.

There are $M$ customers shopping in a supermarket, and each of them, $m_i$, will be ready to check out at time $t_i$, and it takes time $s_i$ for him/her to check out. However, there are only $N$ service counters, and each of them can only serve one customer at a time. If a customer is ready to check out but all service counters are busy, then he/she will wait in a queue, until a service counter becomes available. The customers will wait in the queue in a first-come-first-serve order. Your task is to compute the total waiting time of all customers.

For example, if there are two service counters $c_1$ and $c_2$, four customers arriving at time $0$, $5$, $10$, $15$, and will spend time $20$, $20$, $20$, $20$ during checkout, respectively. The first customer $m_1$ can be served immediately at $c_1$ without waiting, and the second customer $m_2$ can also be served immediately at $c_2$ without waiting. However, when $m_3$ arrives at time $10$, he has to wait in the queue because all the counters are busy, and so does $m_4$ when he arrives at time $15$. After $m_1$ finishes at time $20$, the first customer in a queue, who is $m_3$, could finally be served. As a result $m_3$ waits in the queue for $10$ seconds, and will be served at time $20$ at $c_1$. Similarly customer $m_4$ will be served at time $25$ at counter $c_2$, after he waits in the queue for $10$ seconds. The total waiting time of all customers is therefore $20$ seconds.

Hint

You only need to maintain the ready time of all counters, and always go to the earliest available counter for checking out.

Input Format

Input contains one test case. The first line contains two integers $N$ and $M$, indicating the number of the service counters and the number of the customers.

For the following $M$ lines, each line contains two integers $t_i$ and $s_i$, indicating the $i_{th}$ customer arrives at time $t_i$, and had to spend $s_i$ seconds while checking out.

Note that the $M$ lines will be ordered by arriving time $t$ ascending, and if multiple customers have the same arriving time, then their order in waiting queue should be the same as the input order.

Technical limitation

  • $1 \leq N \leq 1024$
  • $0 \leq M \leq 10^6$
  • $0 \leq t_i \leq 10^4$
  • $0 \leq s_i \leq 10^2$

Output Format

Output one line with one integer indicating the total waiting time.

Sample Input 1

2 4
0 20
5 20
10 20
15 20

Sample Output 1

20

Sample Input 2

1 3
0 20
0 20
0 20

Sample Output 2

60

Discussion