/* paiza POH! Lite
 * result:
 * http://p...content-available-to-author-only...a.jp/poh/kirishima/result/e0dc73382fe071c8016bf5fdd884277b
 * 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;
	
	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++) {
		for (j = 0; j <= w; j++) {
			if (q[i] <= j) {
				x = a[i][j];
				y = a[i][j - q[i]] + r[i];
				a[i + 1][j] = (x > y) ? x : y;
			} else {
				a[i + 1][j] = a[i][j];
			}
		}
	}
	
	printf("%d\n", p - a[n][w]);
	
	return 0;	
}