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

typedef struct _data {
	int q;
	int r;
} DATA, *PDATA;

int m, n;
DATA data[50];

int min = 250000000;

DATA temp[5][1024];
int s[5];

int sort_q(void *a, void *b) {
	PDATA pa = (PDATA)a;
	PDATA pb = (PDATA)b;
	return pb->q - pa->q;
}

void foo(int sum_q, int sum_r, int k) {
	int i, q, r;
	
	for (i = 0; i < s[k] && temp[k][i].q > 0; i++) {
		q = sum_q + temp[k][i].q;
		r = sum_r + temp[k][i].r;
		if (q >= m) {
			if (r < min) {
				min = r;
			}
		} else if (k < 4) {
			foo(q, r, k + 1);
		} else {
			return;
		}
	}
}

int main(void) {
	int i, j, k, l;
	
	scanf("%d", &m);
	scanf("%d", &n);
	
	for (i = 0; i < n; i++) {
		scanf("%d %d", &data[i].q, &data[i].r);
	}
	
	for (i = 0; i < 1024; i++) {
		for (j = 0; j < 10; j++) {
			if ((i >> j) & 1) {
				for (k = 0; k < 5; k++) {
					temp[k][i].q += data[j + k * 10].q;
					temp[k][i].r += data[j + k * 10].r;
				}
			}
		}
 	}
	
	for (i = 0; i < 5; i++) {
		qsort(temp[i], 1024, sizeof(DATA), sort_q);
	}
	
	for (i = 0; i < 5; i++) {
		k = l = 0;
		for (j = 0; j < 1024; j++) {
			if (temp[i][j].q == temp[i][k].q) {
				if (temp[i][j].r < temp[i][k].r) {
					k = j;
				}
			} else {
				temp[i][l] = temp[i][k];
				l++;
				k = j;
			}
		}
		temp[i][l].q = 0;
		temp[i][l].r = 0;
		s[i] = l + 1;
	}

	foo(0, 0, 0);
	
	printf("%d\n", min);
	
	return 0;
}