#include<bits/stdc++.h>
using namespace std;
int cmp(int x,int y)
{
    if(x>y)	return x;
    else return y;
}
int signle_time[1000005],price[1000005],dp[10000005]={0};
int main()
{
    int time,num;
    int max=0;
    int i,j;
    
    cin>>time>>num;
    for(i=1;i<=num;i++)	cin>>signle_time[i]>>price[i];
 
    for(i=1;i<=num;i++)
    {
        for(j=signle_time[i];j<=time;j++)
            {
            	dp[j]=cmp(dp[j],dp[j-signle_time[i]]+price[i]);
                if(dp[j]>max)	max=dp[j];
            }
    }
    cout<<max<<endl;
    return 0;
}