#2627 Garbage Collection

1 s   128 MB  

Description

Garbage truck is collecting garbage on its route starting at the dump and collecting garbage from pick up points in order (closest first). Garbage truck returns to the dump and empties its contents if it either

  1. is full or
  2. cannnot load the garbage at the current point because it will put the load over the weight limit (the truck driver has no way of knowing the weight of the garbage at a particular pick up point until the truck reaches that point) or
  3. there are no more pick up points left

The pick up run ends when the truck returns to the dump after the case #3. In the case where both rule #1 and rule #3 apply, we consider only the latter one (the run is over). Also note that there are no partial pick ups (e.g. this is not allowed: get a portion of garbage at some point until truck is full and come back for the rest).

Given the weight limit that truck can carry and the list of pick up points with garbage weights, what is the distance that the truck will cover following the rules above?

Input

Input starts with an integer $T$ on the first line, the number of test cases.

Each case starts with the line with two integers $W$ and $N$, the weight limit and the number of pick up points, respectively.


Then $N$ lines follow, each containing integers $x_i$ and $w_i$, the distance from the dump and the weight of the garbage at the pick up point respectively.
 

Constraints are as given: $1\leq W \leq 1000$, $1 \leq N \leq 1000$, $0 < x_i \leq 100,000$, $1 \leq w_i \leq W$. Distances are distinct and given in order, i.e. for each $i < j$, $x_i < x_j$.

 

 

Output

For each test case output an integer on a line - the distance covered by the garbage truck.

Sample Input

Sample Output

3
2 2
1 1
2 2
6 3
1 1
2 2
3 3
3 3
1 2
2 2
3 1
8
6
10

Source

The Alberta Collegiate Programming Contest (ACPC) 2012