//动态规划-01背包-二维
#include<iostream>
using namespace std;
const int N=1e3+5;
int n,m,t[N],v[N],dp[N][N];
//dp[i][j]:前i个药材中选则花费的时间为j的价值的集合
//性质:max
//状态计算:
//  不选择:dp[i][j]=dp[i-1][j];
//    选择:dp[i][j]=dp[i-1][j-t[i]]+v[i]
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>t[i]>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++){
            dp[i][j]=dp[i-1][j];
            if(j>=t[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-t[i]]+v[i]);
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}

//动态规划-01背包-一维
#include<iostream>
using namespace std;
const int N=1e3+5;
int n,m,t[N],v[N],dp[N];
//dp[j]:前n个药材中选则花费的时间为j的价值的集合
//性质:max
//状态计算:
//  不选择:dp[j]=dp[j];
//    选择:dp[j]=dp[j-t[i]]+v[i]
int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>t[i]>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=m;j>=t[i];j--){
            dp[j]=max(dp[j],dp[j-t[i]]+v[i]);
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}