/* paiza POH! Lite
 * result:
 * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/050e7c0556cbbf5791a5018fd30b558f
 * author: Leonardone @ NEETSDKASU
 */
#include <stdio.h>
#include <stdlib.h>

int a[51][500001];
int q[51];
int r[51];

int main(void) {
	
	int m;
	int n;
	
	int w = 0, p = 0;
	
	int i, j, x, y;
	int *t0, *t1;
	
	
	scanf("%d", &m);
	scanf("%d", &n);
	
	for (i = 0; i < n; i++) {
		scanf("%d %d", &q[i], &r[i]);
		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];
			}
		}
	}
	
	printf("%d\n", p - a[n][w]);
	
	return 0;	
}