# 50055. Waiting Time at Supermarket

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

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 40 205 2010 2015 20


## Sample Output 1

20


## Sample Input 2

1 30 200 200 20


## Sample Output 2

60