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