#include <stdio.h>
#include <stdlib.h>
int t,m;
int w[10000];
int v[10000];
int dp[1000][10000];

int max(int a,int b)
{
    if(a>=b)return a;
    else return b;
}

int main()
{
    while(scanf("%d%d",&t,&m)!=EOF)
    {
        //dp[i][j]采前i个草药，时间为j的最大价值
        for(int i=0; i<m; i++)scanf("%d%d",&w[i],&v[i]);
        //初始化
        for(int i=0; i<=t; i++){
            if(i>=w[0])dp[0][i]=v[0];
            else dp[0][i]=0;
        }
        for(int i=0; i<m; i++){
            dp[i][0]=0;
        }
        //赋值
        for(int i=1; i<m; i++)
        {
            for(int j=t; j>=1; j--)
            {
                if(j>=w[i])dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);
                else dp[i][j]=dp[i-1][j];

            }

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

    }



    return 0;
}