#include <bits/stdc++.h>
using namespace std;
const int N = 21;
int W, n, t[N], w[N];
int mxt[1 << N], sumw[1 << N];
int dp[N];
int main() {
	memset(dp, 0x3f, sizeof dp);
	cin >> W >> n;
	for (int i = 0; i < n; i++) {
		cin >> t[i] >> w[i];
	}
	int ALL = (1 << n) -1;
	for (int i = 0; i <= ALL; i++) {
		for (int j = 0; j < n; j++) {
			if ((i >> j) & 1) {
				sumw[i] += w[j];
				mxt[i] = max(mxt[i], t[j]);
			}
		}
	}
	dp[0] = 0;
	for (int i = 0; i <= ALL; i++) {
		for (int j = i; j; j = i & (j - 1)) {
			if (sumw[j] <= W) {
				dp[i] = min(dp[i], dp[i ^ j] + mxt[j]);
			}
		}
	}
	cout << dp[ALL];
	return 0;
}