#include<bits/stdc++.h>
using namespace std;
int n,V,w[105],v[105]; 
int dp[105][1005];
int main()
{
    cin>>V>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
        for(int j=0;j<=V;j++)
            if(w[i]>j)dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
    cout<<dp[n][V];
    return 0;
} 

#include<bits/stdc++.h>
using namespace std;
int sj,sl;
int w[105],v[105];
int dp[105][1005];
int main()
{
    cin>>sj>>sl;
    for(int i=1;i<=sl;i++)
        cin>>w[i]>>v[i];
    for(int i=1;i<=sl;i++)
        for(int j=0;j<=sj;j++)
            if(j>=w[i])
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
            else
                dp[i][j]=dp[i-1][j];
    cout<<dp[sl][sj];
    return 0;
}