Vladimir would like to prepare a present for his wife: they have an anniversary! He decided to buy her exactly n flowers.

Vladimir went to a flower shop, and he was amazed to see that there are m types of flowers being sold there, and there is unlimited supply of flowers of each type. Vladimir wants to choose flowers to maximize the happiness of his wife. He knows that after receiving the first flower of the i-th type happiness of his wife increases by a_i and after receiving each consecutive flower of this type her happiness increases by b_i. That is, if among the chosen flowers there are x_i > 0 flowers of type i, his wife gets a_i + (x_i - 1) ⋅ b_i additional happiness (and if there are no flowers of type i, she gets nothing for this particular type).

Please help Vladimir to choose exactly n flowers to maximize the total happiness of his wife.

Input

The first line contains the only integer t (1 ≤ t ≤ 10 000), the number of test cases. It is followed by t descriptions of the test cases.

Each test case description starts with two integers n and m (1 ≤ n ≤ 10^9, 1 ≤ m ≤ 100 000), the number of flowers Vladimir needs to choose and the number of types of available flowers.

The following m lines describe the types of flowers: each line contains integers a_i and b_i (0 ≤ a_i, b_i ≤ 10^9) for i-th available type of flowers.

The test cases are separated by a blank line. It is guaranteed that the sum of values m among all test cases does not exceed 100 000.

Output

For each test case output a single integer: the maximum total happiness of Vladimir's wife after choosing exactly n flowers optimally.

Example

Input


2
4 3
5 0
1 4
2 2

5 3
5 2
4 2
3 1


Output


14
16

Note

In the first example case Vladimir can pick 1 flower of the first type and 3 flowers of the second type, in this case the total happiness equals 5 + (1 + 2 ⋅ 4) = 14.

In the second example Vladimir can pick 2 flowers of the first type, 2 flowers of the second type, and 1 flower of the third type, in this case the total happiness equals (5 + 1 ⋅ 2) + (4 + 1 ⋅ 2) + 3 = 16.


import java.util.*;
import java.lang.*;
import java.io.*;   
import java.math.*;
public class Prac{     
    static class InputReader { 
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        public InputReader(InputStream st) {
            this.stream = st;
        } 
        public int read() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } 
                catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
        public int ni() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        } 
        public long nl() {
            int c = read();
            while (isSpaceChar(c)) {
            c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        } 
        public int[] nia(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        } 
        public int[] nia1(int n) {
            int a[] = new int[n+1];
            for (int i = 1; i <=n; i++) {
                a[i] = ni();
            }
            return a;
        } 
        public long[] nla(int n) {
            long a[] = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        } 
        public long[] nla1(int n) {
            long a[] = new long[n+1];
            for (int i = 1; i <= n; i++) {
                a[i] = nl();
            }
            return a;
        } 
        public Long[] nLa(int n) {
            Long a[] = new Long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        } 
        public Long[] nLa1(int n) {
            Long a[] = new Long[n+1];
            for (int i = 1; i <= n; i++) {
                a[i] = nl();
            }
            return a;
        } 
        public Integer[] nIa(int n) {
            Integer a[] = new Integer[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        } 
        public Integer[] nIa1(int n) {
            Integer a[] = new Integer[n+1];
            for (int i = 1; i <= n; i++) {
                a[i] = ni();
            }
            return a;
        } 
        public String rs() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                    c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        } 
        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        } 
    }
    public static class Key {
        private final int x, y;
        public Key(int x, int y) {
            this.x = x; this.y = y;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Key)) return false;
            Key key = (Key) o;
            return x == key.x && y == key.y;
        }
        @Override
        public int hashCode() {
            int result = x;
            result = 31 * result + y;
            return result;
        }
    }
    static class Pair implements Comparable<Pair>{
            int x,y;
            Pair(int a,int b){
                    x=a;y=b;
            }
            @Override
            public int compareTo(Pair p) {
                    if(x==p.x) return y-p.y;
                    return x-p.x;
            }
    }
    static PrintWriter w = new PrintWriter(System.out);
    static long mod1=998244353L,mod=1000000007;
    //static int r[]={0,1,0,-1}, c[]={1,0,-1,0};
    
    static int lb(long val){
        int l=0,r=temp.length-1,ans=-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(temp[mid]>=val){
                r=mid-1;
                ans=mid;
            }
            else{
                l=mid+1;
            }
        }
        return ans;
    }
    static void shuffleArray(){
        int n = temp.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i){
            long tmp = temp[i];
            int randomPos = i + rnd.nextInt(n-i);
            temp[i] = temp[randomPos];
            temp[randomPos] = tmp;
        }   
    }
    static long a[],b[],pSum[],temp[],n;
    public static void main(String [] args){
        InputReader sc=new InputReader(System.in); 
        int t=sc.ni();
        String f="abacaba";
        while(t-->0){
            int n=sc.ni();
            int m=sc.ni();
            a=new long[m];
            b=new long[m];
            pSum=new long[m+1];
            temp=new long[m];
            for(int i=0;i<m;i++){
                a[i]=sc.ni();
                b[i]=sc.ni();
                temp[i]=a[i];
            }
            shuffleArray();
            Arrays.sort(temp);
            long last=0;
            for(int i=m-1;i>=0;i--){
                pSum[i]=temp[i]+last;
                last=pSum[i];
            }
            long ans=0;
            for(int i=0;i<m;i++){
                int c=n;
                int in=lb(b[i]+1);
                long sum=a[i];
                c--;
                if(in==-1){
                    sum+=((long)c*b[i]);
                }
                else{
                    if(temp[in]<=(a[i])){
                        sum-=a[i];
                        c++;
                    }
                   
                    if(c>=(m-in)){
                        c-=(m-in);
                        sum+=(pSum[in]);
                        sum+=((long)c*b[i]);
                    }
                    else {
                        sum+=pSum[m-c];
                        c=0;
                    }
                }
                
                ans=Math.max(ans,sum);
            }
            w.println(ans);
        }
        w.close();
    }
}