// Original C++ solution (slower):


#include <stdio.h>

#include <string.h>

#include <limits.h>

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <map>

#include <set>

#include <stack>

#include <queue>



typedef unsigned long long ULLONG;

typedef long long LLONG;

static const LLONG MOD_NUM = 1000000007;



template<class _T> static void getint(_T& a) {

	const char* fmt = " %d";

	if (sizeof(_T) == sizeof(long long)) {

		fmt = " %lld";

	}



	if (scanf(fmt, &a) < 0) {

		printf("g1int Error\n");

	}

}

template<class _T> static void getint(_T& a, _T& b) {

	const char* fmt = " %d %d";

	if (sizeof(_T) == sizeof(long long)) {

		fmt = " %lld %lld";

	}



	if (scanf(fmt, &a, &b) < 0) {

		printf("g2int Error\n");

	}

}

template<class _T> static void getint(_T& a, _T& b, _T& c) {

	const char* fmt = " %d %d %d";

	if (sizeof(_T) == sizeof(long long)) {

		fmt = " %lld %lld %lld";

	}



	if (scanf(fmt, &a, &b, &c) < 0) {

		printf("g3int Error\n");

	}

}



static void ABC153E();



#if 1

int main()

{

	ABC153E();

	fflush(stdout);

	return 0;

}

#endif



static void ABC153E()

{

	int H, N;

	getint(H, N);



	std::vector<std::pair<int, int>> magics(N);

	for (int i = 0; i < N; i++) {

		getint(magics[i].first, magics[i].second);

	}



	std::vector<std::vector<int>> dp(H + 1, std::vector<int>(N + 1, (int)MOD_NUM));

	std::fill(dp[0].begin(), dp[0].end(), 0);

	for (int h = 1; h <= H; h++) {

		for (int m = 1; m <= N; m++) {

			if ((magics[m - 1].first >= h) && (magics[m - 1].second < dp[h][m])) {

				dp[h][m] = magics[m - 1].second;

			}

			if (h >= magics[m - 1].first) {

				dp[h][m] = std::min(dp[h - magics[m - 1].first][m] + magics[m - 1].second, dp[h][m]);

			}

			dp[h][m] = std::min(dp[h][m], dp[h][m - 1]);

		}

	}

	printf("%d\n", dp[H][N]);

}


// Optimized solution to the same problem (faster):


#include <stdio.h>

#include <string.h>

#include <limits.h>

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

#include <map>

#include <set>

#include <stack>

#include <queue>



typedef unsigned long long ULLONG;

typedef long long LLONG;

static const LLONG MOD_NUM = 1000000007;



template<class _T> static void getint(_T& a) {

	const char* fmt = " %d";

	if (sizeof(_T) == sizeof(long long)) {

		fmt = " %lld";

	}



	if (scanf(fmt, &a) < 0) {

		printf("g1int Error\n");

	}

}

template<class _T> static void getint(_T& a, _T& b) {

	const char* fmt = " %d %d";

	if (sizeof(_T) == sizeof(long long)) {

		fmt = " %lld %lld";

	}



	if (scanf(fmt, &a, &b) < 0) {

		printf("g2int Error\n");

	}

}

template<class _T> static void getint(_T& a, _T& b, _T& c) {

	const char* fmt = " %d %d %d";

	if (sizeof(_T) == sizeof(long long)) {

		fmt = " %lld %lld %lld";

	}



	if (scanf(fmt, &a, &b, &c) < 0) {

		printf("g3int Error\n");

	}

}



static void ABC153E();



#if 1

int main()

{

	ABC153E();

	fflush(stdout);

	return 0;

}

#endif



static void ABC153E()

{

	int H, N;

	getint(H, N);



	std::vector<std::pair<int, int>> magics(N);

	for (int i = 0; i < N; i++) {

		getint(magics[i].first, magics[i].second);

	}



	std::vector<int> cost(H + 1, (int)MOD_NUM);

	cost[0] = 0;

	for (int h = 1; h <= H; h++) {

		for (int m = 0; m < N; m++) {

			if ((h < magics[m].first) && (cost[h] > magics[m].second)) {

				cost[h] = magics[m].second;

			}

			if (h >= magics[m].first) {

				cost[h] = std::min(cost[h], (cost[h - magics[m].first] + magics[m].second));

			}

		}

	}



	printf("%d\n", cost[H]);

}


// Fastest known solution for this problem: