#include<bits/stdc++.h>
#define pb emplace_back
#define ALL(i) begin(i), end(i)
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) cerr << "[" << #args << "] = ", kout(args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
void debug(...) {}
#endif
const int maxn = 16, inf = 1e9;
int lim, n;
int dp[1<<maxn], t[maxn], w[maxn], cost[1<<maxn];

int solve() {
    for (int i = 1;i < 1<<n;++i) {
        int allw = 0, allt = 0;
        for (int j = 0;j < n;++j) if (i>>j&1)
            allw += w[j], allt = max(allt, t[j]);

        if (allw > lim)
            cost[i] = inf;
        else
            cost[i] = allt;
    }
    fill(dp+1, dp+(1<<n), inf);

    for (int i = 1;i < 1<<n;++i) {
        if (i == (i&-i)) {
            dp[i] = cost[i];
            continue;
        }
        int sub = i - (i&-i);
        for (int s = sub;s &= sub;--s)
            dp[i] = min(dp[i], dp[s] + dp[i ^ s]);
//      for (int s = i-1;s &= (i);--s)
//          dp[i] = min(dp[i], dp[s] + dp[i ^ s]);
//
        dp[i] = min(dp[i], cost[i]);
    }
    return dp[(1<<n)-1];
}
signed main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> lim >> n;
    for (int i = 0;i < n;++i)
        cin >> t[i] >> w[i];
    cout << solve() << '\n';

}