#include<iostream>
#include<algorithm>
using namespace std;

struct pills{
    int time;
    int price;
};

bool cmp(struct pills A,struct pills B){
    return A.time<B.time;
}

class Pick{
    private:
        struct pills* pp;
        int* Result;
        int num;
    public:
        Pick(int n,struct pills* P);
        int Dynamic(int total_time);
        ~Pick(){delete[]pp,delete[]Result;}
};

int Pick::Dynamic(int total_time){
    int **Result=new int*[num+1];
    for(int i=0;i<num+1;i++){
        Result[i]=new int[total_time+1];
    }
    for(int i=0;i<num+1;i++){
        for(int j=0;j<total_time+1;j++){
            Result[0][j]=0;
            Result[i][0]=0;
        }
    }

    for(int i=1;i<=num;i++){
        for(int j=1;j<=total_time;j++){
            if(pp[i].time>j)
            Result[i][j]=Result[i-1][j];
            else
            Result[i][j]=max(Result[i-1][j],Result[i-1][j-pp[i].time]+pp[i].price);
        }
    }

    return Result[num][total_time];
}

Pick::Pick(int n,struct pills* P){
    Result=new int[10000000];
    for(int i=0;i<10000000;i++){
        Result[i]=0;
    }
    num=n;
    pp=new pills[n];
    for(int i=1;i<=num;i++){
        pp[i]=P[i-1];
    }
}

int main(){
    int T,M;
    cin>>T>>M;
    pills* P=new pills[M];
    for(int i=0;i<M;i++){
        cin>>P[i].time>>P[i].price;
    }
    sort(P,P+M,cmp);
    Pick liu(M,P);
    cout<<liu.Dynamic(T)<<endl;
    return 0;
}