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

class Main
{
	
	static int[][] a = new int[51][500001];
	static int[] q = new int[51];
	static int[] r = new int[51];

	public static void main (String[] args) throws java.lang.Exception
	{
		
		int m;
		int n;
		
		int w = 0, p = 0;
		
		int i, j, x, y;
		int[] t0, t1;
		
		Scanner sc = new Scanner(System.in);
		m = sc.nextInt();
		n = sc.nextInt();

		for (i = 0; i < n; i++) {
			q[i] = sc.nextInt();
			r[i] = sc.nextInt();
			w += q[i];
			p += r[i];
		}
		w -= m;
		
		for (i = 0; i < n; i++) {
			t0 = a[i];
			t1 = a[i + 1];
			for (j = 0; j <= w; j++) {
				if (q[i] <= j) {
					x = t0[j];
					y = t0[j - q[i]] + r[i];
					t1[j] = (x > y) ? x : y;
				} else {
					t1[j] = t0[j];
				}
			}
		}
		
		System.out.println(p - a[n][w]);

	}
}