EQ - Electronic queue

no tags 

The train station has just used a new electronic queue system. Now passengers who want to buy tickets have to get the service ordering number and wait until it is his turn.

In this station, there are N cashiers; each can serve one passenger at a time. When it’s your turn, you will go to an assigned cashier to chose a ticket and pay for it. If you want to buy K tickets it will take you 5 minutes to chose the train, the time, the seats, etc and K more minutes for your tickets to be printed. If there are several available cashiers, a passenger would be assigned to the one with the lowest number.

Given the arrival time of passengers at the station and the amount of tickets they want to buy, your task is to calculate the total time P passengers spend buying their tickets (waiting time and buying time).

Input

The first line is C, the number of test cases. For each test case:

  • The first line is N – number of cashiers.
  • The next line consists of P – the number of passengers.
  • The next P lines contain a pair of integers: the arrival time and the number of tickets he wants to buy.
  • The arrival time of these P passengers will be distinct and will be sorted increasingly.

Output

For each test case, print total time of P passengers spend buying their tickets.

Limits

1 <= C <= 15
1 <= N <= 50
1 <= P <= 10000
All others numbers in the input are positive and less than 1000.

Example

Input:
1
2
3
1 1
2 10
3 2

Output:
32

hide comments
slothsphereoj: 2024-03-07 05:13:23

This is, overall, a simple question.
It just that a person can approach a cashier immediately after a passenger bought all tickets, costed me 1 WA.

An example using the sample test case:

passenger 1: Bought all tickets at time = 7. (1+5+1)
waiting time=0, time to buy tickets=5+1=6, total time = 0+6=6.

passenger 2: Bought all tickets at time = 17 (2+5+10)
waiting time=0, time to buy tickets=5+10=15, total time = 0+15=15.

passenger 3: Bought all tickets at time = 14. (7+5+2), NOT starting at time=8 and ends at 15.
waiting time=(7-3)=4, time to buy tickets=5+2=7, total time = 4+7=11.

[INPUT]
4
2
4
1 1
2 10
3 2
4 10
3
4
5 327
10 224
34 213
100 10
5
7
5 55
17 1
100 324
245 1
568 66
643 24
988 100
2
3
1 1
2 10
3 2

[OUTPUT]
57
933
606
32


Added by:sieunhan
Date:2009-11-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:ACM Vietnam Practice