Garbage Collection

A garbage truck starts at the dump at position 0. All pickup points lie on the same straight line. The truck visits the points in increasing order of distance from the dump and must load all trash at a point at once.

The truck returns from its current position to the dump and empties its load in any of the following situations:

1. After loading trash, its load becomes exactly equal to its capacity.
2. Loading the trash at the current point would make the load exceed its capacity.
3. There are no more pickup points to visit.

In the second situation, the truck has already arrived at the current point. It returns to the dump before loading, comes back to the same point, and then loads that point's trash. It is not allowed to take only part of a point's trash.

Given the truck capacity and each point's distance and trash amount, compute the total distance the truck travels until all trash has been collected and the truck has returned to the dump.

The first line contains the number of test cases T.

For each test case, the first line contains the truck capacity W and the number of pickup points N. (1 <= W <= 1000, 1 <= N <= 1000)

Each of the next N lines contains the distance x_i from the dump to the i-th point and the amount of trash w_i at that point. All x_i values are distinct, and the points are given in increasing order of x_i. (0 <= x_i <= 100000, 1 <= w_i <= W)

For each test case, output the total distance traveled until the truck collects all trash and returns to the dump.