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.io.*;
import java.util.*;
import java.util.concurrent.TimeUnit;

public class c1379 implements Runnable{
	
    public static void main(String[] args) {
    	try{
            new Thread(null, new c1379(), "process", 1<<26).start();
        }
        catch(Exception e){
            System.out.println(e);
        }
    }
	public void run() {
		FastReader scan = new FastReader();
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		//PrintWriter out = new PrintWriter("file.out");
		Task solver = new Task();
		int t = scan.nextInt();
		//int t = 1;
		for(int i = 1; i <= t; i++) solver.solve(i, scan, out);
		out.close();
	}

	static class Task {
		static final int inf = Integer.MAX_VALUE;

		public void solve(int testNumber, FastReader sc, PrintWriter out) {
			int N = sc.nextInt();
			int M = sc.nextInt();
			
			tup[] flowers = new tup[M];
			Long[] pSum = new Long[M];
			long[] firstFlower = new long[M];
			for(int i = 0; i < M; i++) {
				flowers[i] = (new tup(sc.nextInt(), sc.nextInt()));
				pSum[i] = (long) flowers[i].a;
			}
			
			sort(pSum);
			firstFlower[0] = pSum[0];
			for(int i = 1; i < M; i++) {
				firstFlower[i] = pSum[i];
				pSum[i] += pSum[i-1];
			}
			//System.out.println(Arrays.toString(firstFlower));
			
			long best = 0;
			for(int i = 0; i < M; i++) {
				
				int flowersToChoose = (flowers[i].a > flowers[i].b) ?  N : N-1;
				long happiness = (flowers[i].a > flowers[i].b) ?  0 : flowers[i].a;
				// binary search for all flowers that have a better ai than this flower's bi
				int lo = 0, hi = M-1;
				while(lo < hi) {
					int mid = (lo + hi) / 2;
					if(firstFlower[mid] > flowers[i].b) {
						lo = mid+1;
					} else {
						hi = mid-1;
					}
				}
				while(lo < M && firstFlower[lo] >= flowers[i].b)
					lo++;
				while(lo == M || lo >= 0 && firstFlower[lo] < flowers[i].b)
					lo--;
				// lo is the lowest flower that is greater than or equal to this flower's bi
				//System.out.println(i + " " + lo);
				
				// Case one: only take first flowers
				if(flowersToChoose <= lo) {
					if(flowersToChoose >= 1)
						happiness += pSum[flowersToChoose-1];
					
				// Case two: take lo first flowers, then take bis
				} else {
					if(lo > -1)
						happiness += pSum[lo];
					flowersToChoose -= (lo+1);
					happiness += (flowersToChoose * flowers[i].b);
				}
				best = Math.max(best, happiness);
			}
			
			out.println(best);
		}
	}
	static long binpow(long a, long b, long m) {
		a %= m;
		long res = 1;
		while (b > 0) {
			if ((b & 1) == 1)
				res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
	}
	static void sort(int[] x){
		shuffle(x);
		Arrays.sort(x);
	}
	static void sort(Long[] x){
		shuffle(x);
		Arrays.sort(x, Collections.reverseOrder());
	}
	static class tup implements Comparator<tup>{
		long a, b;
		tup(int a,int b){
			this.a=a;
			this.b=b;
		}
		public tup() {
		}
		@Override
		public int compare(tup o1, tup o2) {
			return Long.compare(o2.b, o1.b);
		}
		
		@Override
	    public int hashCode() {
			return Objects.hash(a, b);
	    }
 
	    @Override
	    public boolean equals(Object obj) {
	    	if (this == obj)
                return true;
	    	if (obj == null)
                return false;
	    	if (getClass() != obj.getClass())
                return false;
	    	tup other = (tup) obj;
	    	return a==other.a && b==other.b;
	    }
	    
	    @Override
	    public String toString() {
	    	return a + " " + b;
	    }
	}
	
	static void shuffle(int[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			int temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	static void shuffle(Long[] a) {
		Random get = new Random();
		for (int i = 0; i < a.length; i++) {
			int r = get.nextInt(a.length);
			long temp = a[i];
			a[i] = a[r];
			a[r] = temp;
		}
	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

}