EQ - Electronic queue

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 cashers; 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.


Sample input
1
2
3
1 1
2 10
3 2


Sample output
32


Được gửi lên bởi:sieunhan
Ngày:2009-11-29
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:ACM Vietnam Practice

hide comments
2012-12-13 16:04:46 T-7
P<=10000. Arrival times are distinct and <=1000. Not logic at all =))
2010-06-08 21:48:36 Trần Hải Ðãng
Kể ra bài này thiếu chú ý một chút là die, mình là 1 ví dụ :D
2010-04-13 22:49:20 dhkhtn
phai su dung long long long long long long ... int de AC
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.