#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=,S=(<<)+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int m,n,a[N],w[N];

int f[S];

int main(){

    //freopen("in","r",stdin);

    m=read();n=read();

    for(int i=;i<n;i++){

        a[i]=read(),w[i]=read();

        f[<<i]=a[i];

    }

    int All=<<n;

    memset(f,0x3f,sizeof(f));

    f[]=;

    for(int s=;s<All;s++){

        int sum=,slow=;

        for(int i=;i<n;i++)

            if((<<i)&s) sum+=w[i],slow=max(slow,a[i]);

        if(sum<=m) f[s]=slow;

        else for(int t=s&(s-);t;t=s&(t-)) f[s]=min(f[s],f[t]+f[s^t]);

    }

    printf("%d",f[All-]);

}