#include <bits/stdc++.h>
using namespace std;
vector <int> w,v;
int dp[2100][2100];
int n,t,a,b,mx=0;
int main()
{
    scanf("%d %d",&t,&n);
    for (int i=0;i<n;i++)
    {
        scanf("%d %d",&a,&b);
        w.push_back(a);
        v.push_back(b);
    }
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<=t;j++)
        {
            if (!i)
                dp[i][j]= (w[i]<=j ? v[i] : 0);
            else
            {
                dp[i][j]=dp[i-1][j];
                if (w[i]<=t)
                {
                    dp[i][j]= max (dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
                }
            }


        }
    }
    printf("%d\n",dp[n-1][n-1]);
}