#include<iostream>#include<cstdio>#include<cstring>using namespace std;int t[510],f[510],p[100010],n,k;long long ans;int main(){    cin>>k;    cin>>n;    for(int i=1;i<=n;i++)      cin>>t[i]>>p[i],ans+=p[i];    for(int i=1;i<=n;i++)    {        for(int j=k;j>=t[i];j--)        {            f[j]=max(f[j],f[j-t[i]]+p[i]);        }    }    printf("%d",ans-f[k]);        return 0;}