Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given an array A of size N. Initially, the array is filled with 0-s.

There are M types of operations that you can perform on array A. The i^{th} operation can be described by two integers (x_{i}, y_{i}). In this operation, you choose a set of indices S such that

1 ≤ j ≤ N,
$(j \bmod y_{i}) \neq 0$,
A_{j} = 0,

, then you set A_{j} = x_{i} for all $j \in$ S.

You can perform the operations in any order, but one type of operation can't be done more than once. What is the maximum sum of integers of the array A you obtain if you perform the M operations optimally?

For example, consider the array A = [0, 0, 0, 0].
Suppose x = 3, y = 2. Here you can choose indices 1 and 3 and set A_{1} = A_{3} = 3. So the array A becomes [3, 0, 3, 0]. In this operation you can't choose the indices 2 and $4 because (2 \bmod 2) = 0, (4 \bmod 2) = 0$.
Suppose x = 5, y = 3 and you set A_{2} = 5. So the array A becomes [3, 5, 3, 0]. Here you can't choose index 1 because A_{1} > 0 and index $3 because (3 \bmod 3) = 0$ and A_{3} > 0. However, you could also set A_{4} = 5.

Suppose x = 4, y = 4. Now you can't choose any index because A_{j} > 0 for all 1 ≤ j ≤ 3 and $(4 \bmod 4) = 0.$ So the array remains same.

Note: Since input-output is large, prefer using fast input-output methods.

------ Input Format ------

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• Each testcase contains M + 1 lines of input.
• The first line of each test case contains two space-separated integers N, M.
• M lines follow. For each valid i, the i^{th} of these lines contains two space-separated integers x_{i}, y_{i} - parameters of the i^{th} operation.

------ Output Format ------

For each test case, output in a single line the maximum sum of integers of the array A after M operations.

------ Constraints ------

$1 ≤ T ≤ 12600$
$1 ≤ N ≤ 10^{9}$
$1 ≤ M ≤ 10^{5}$
$1 ≤ x_{i} ≤ 10^{9}$
$2 ≤ y_{i} ≤ 10^{9}$
- The sum of $M$ over all test cases does not exceed $10^{6}$.

------ subtasks ------

Subtask #1 (100 points): original constraints

----- Sample Input 1 ------
3
10 1
5 2
8 2
5 2
6 3
3 2
2 2
1 3
----- Sample Output 1 ------
25
41
5
----- explanation 1 ------
Test case $1$: Optimal filling is $[5, 0, 5, 0, 5, 0, 5, 0, 5, 0]$.

Test case $2$: Optimal filling is $[6, 6, 5, 6, 6, 0, 6, 6]$.

Test case $3$: Optimal filling is $[2, 1, 2]$.

见题面

见题面