#include<bits/stdc++.h>
using namespace std;
int n,t,dp[1010][110]={0},ans=0;
struct yao
{
int price;
int time;
}a[110];
int main()
{
cin>>t>>n;
for(int i=1;i<=n;i++)cin>>a[i].time>>a[i].price;
for(int i=1;i<=t;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=dp[i][j-1];
if(i-a[j].time>=0)dp[i][j]=max(dp[i][j],dp[i-a[j].time][j-1]+a[j].price);
// cout<<dp[i][j]<<" "<<a[j].price<<" "<<a[j].time<<" ";
ans=max(ans,dp[i][j]);
}
}
cout<<ans;
return 0;
}
