/* paiza POH! Lite
 * result:
 * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/000512911c98eece9b0aa060fa6ce332
 * author: Leonardone @ NEETSDKASU
 */
import java.io.*;
import java.lang.*;
import java.util.*;

class Main
{
	static class Data implements Comparable<Data> {
		public int q;
		public int r;
		public double p;
		public int compareTo(Data o) {
			return (int)(o.p - this.p);
		}
	}
	
	static int parseInt(String str) {
		int len = str.length();
		int n = 0;
		for (int i = 0; i < len; i++) {
			n = n * 10 + (int)(str.charAt(i) - '0');
		}
		return n;
	}

	static Data[] data = new Data[100];
	static int all_q = 0;
	static int all_r = 0;
	
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int m, n, i;
		
		m = parseInt(in.readLine());
		n = parseInt(in.readLine());
		
		for (i = 0; i < n; i++) {
			String[] str = in.readLine().split(" ");
			data[i] = new Data();
			all_q += data[i].q = parseInt(str[0]);
			all_r += data[i].r = parseInt(str[1]);
			data[i].p = (double)data[i].r / (double)data[i].q;
		}
		for (; i < 100; i++) {
			data[i] = new Data();
		}
		
		Arrays.sort(data, 0, n);
		
		int sum_q = 0, sum_r = 0;
		for (i = 0; sum_q < m && i < n; i++) {
			sum_q += data[i].q;
			sum_r += data[i].r;
		}
		
		if (n - i > i) {
			i += 3;
			foo(m, i > n ? n : i);
		} else {
			i -= 5;
			if (i < 0) {
				i = 0;
			}
			bar(m, n - i, i);
		}
		
	}
	
	static void foo(int m, int n) {
		int a0, a1, b0, b1, c0;
		int min, sum_q, sum_r;
		int i;
		 
		if (n > 25) {
			b0 = 0;
			b1 = 1 << (n - 25);
		} else {
			b0 = 1 << n;
			b1 = 0;
		}
		 
		a0 = 1;
		a1 = 0;
		c0 = 1 << 25;
		min = 250000000;
		for (;;) {
			if (a1 > b1) {
				break;
			} else if (a1 == b1 && a0 > b0) {
				break;
			}
			if (a0 == c0) {
				a0 = 0;
				a1++;
			}
			sum_q = sum_r = 0;
			for (i = 0; i < 25; i++) {
				if (1 == ((a0 >> i) & 1)) {
					sum_q += data[i].q;
					sum_r += data[i].r;
				}
				if (1 == ((a1 >> i) & 1)) {
					sum_q += data[i + 25].q;
					sum_r += data[i + 25].r;
				}
			}
			if (sum_q >= m && sum_r < min) {
				min = sum_r;
			}
			a0++;
		}
		System.out.println(min);
	}
	
	static void bar(int m, int n, int d) {
		int a0, a1, b0, b1, c0;
		int min, sum_q, sum_r;
		int i;
		 
		if (n > 25) {
			b0 = 0;
			b1 = 1 << (n - 25);
		} else {
			b0 = 1 << n;
			b1 = 0;
		}
		 
		a0 = 1;
		a1 = 0;
		c0 = 1 << 25;
		min = 250000000;
		for (;;) {
			if (a1 > b1) {
				break;
			} else if (a1 == b1 && a0 > b0) {
				break;
			}
			if (a0 == c0) {
				a0 = 0;
				a1++;
			}
			sum_q = sum_r = 0;
			for (i = 0; i < 25; i++) {
				if (1 == ((a0 >> i) & 1)) {
					sum_q += data[i + d].q;
					sum_r += data[i + d].r;
				}
				if (1 == ((a1 >> i) & 1)) {
					sum_q += data[i + d + 25].q;
					sum_r += data[i + d + 25].r;
				}
			}
			if (all_q - sum_q >= m && all_r - sum_r < min) {
				min = all_r - sum_r;
			}
			a0++;
		}
		System.out.println(min);
	}
	
}