/* paiza POH! Lite
 * result:
 * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/4540e9efffb1299f0915533326575d70
 * author: Leonardone @ NEETSDKASU
 */
import java.io.*;
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;
		
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		m = Integer.parseInt(in.readLine());
		n = Integer.parseInt(in.readLine());

		for (i = 0; i < n; i++) {
			String[] str = in.readLine().split(" ");
			q[i] = Integer.parseInt(str[0]);
			r[i] = Integer.parseInt(str[1]);
			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]);

	}
}