#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct bomba {
	int vaha;
	int sila;
};

/* porovná bomby podle efektivity, tou je sila/vaha */
int bomba_comp(const void * b1, const void * b2) {
	const struct bomba *ib1 = (const struct bomba *)b1;
	const struct bomba *ib2 = (const struct bomba *)b2;
	/* Porovnávám dva zlomky: b1.sila/b1.vaha a b2.sila/b2.vaha, to je stejné
	 * jako porovnat b1.sila*b2.vaha a b2.sila*b1.vaha, jmenovatele jsou totiž kladné
	 * síla je maximálně 10^5, váha max 10^4, takže se to vejde do intu
	 */
	int x = ib1->sila * ib2->vaha;
	int y = ib2->sila * ib1->vaha;
	return x-y;
}

#define min(a,b) ((a<b)?a:b)

#define LONG long long int

int main(void) {

	int V,N;
	scanf("%d %d\n",&V,&N);

	struct bomba bomby[N];
	int soucetsil = 0;

	for (int i=0; i<N; i++) {
		int w,d;
		scanf("%d %d\n",&w,&d);
		bomby[i].vaha = w;
		bomby[i].sila = d;
		soucetsil += d;
	}

	/* bomby teď budou seřazeny podle efektivity vzestupně */
	qsort(bomby, N, sizeof(struct bomba), bomba_comp);

	/* použijeme všechny bomby */
	if (soucetsil==V) {
		LONG energie = 0;
		int komin = V;
		for (int i=N-1; i>=0; i--) {
			energie += komin*bomby[i].vaha;
			komin -= bomby[i].sila;
		}
		printf("%lld\n",energie);

	} else { /* některé bomby můžou zbýt */

		LONG tabulka[2][V+1];
		for (int i=0; i<2; i++)
			for (int j=0; j<V+1; j++)
				tabulka[i][j] = LONG_MAX;

		LONG nejmin = LONG_MAX;

		tabulka[0][V] = 0;
		// pro všechny bomby dle efektivity sestupně
		for (int i=N-1; i>=0; i--) {
			int idbomby = N-i;
			for (int j=V; j>0; j--) {
				// jsme na políčku, kde něco je
				if (tabulka[(idbomby-1)%2][j] < LONG_MAX) {
					// bombu i nepoužijeme...
					tabulka[idbomby%2][j] = min(
							tabulka[(idbomby-1)%2][j], // předchozí řádek
							tabulka[idbomby%2][j] // to, co tam už bylo
						);
					// ...nebo použijeme
					if (j-bomby[i].sila>=0) {//pokud bomba není příliš silná
						tabulka[idbomby%2][j-bomby[i].sila] = min(
								tabulka[(idbomby-1)%2][j] + j*bomby[i].vaha,
								tabulka[(idbomby)%2][j-bomby[i].sila] // to, co tam už bylo
							);
					}
				}
				nejmin = min(nejmin, tabulka[idbomby%2][0]);
			}
		}

		if (nejmin!=LONG_MAX)
			printf("%lld\n",nejmin);
		else // když se komín nedá zbourat
			printf("0\n");
	}

	return 0;
}