#include <stdio.h>
#define inf 999999999

int g[101],v[10101],a[10101],i,j,s,n,k;

int main()
{
    freopen("pusculita.in","r",stdin);
    freopen("pusculita.out","w",stdout);
    
    scanf("%d%d",&s,&n);
    
    for(i=1; i<=n; ++i)
        scanf("%d%d",&g[i],&v[i]);
    for(i=1; i<=10101; ++i)
        a[i]=inf;
    for(i=1; i<=n; ++i)
        for(j=0; j<=s; ++j)
            if(a[j]!=inf)
            {
                if(a[j]+v[i]<a[j+g[i]])
                    a[j+g[i]]=a[j]+v[i];
            }
    printf("%d",a[s]);
}