#include<bits/stdc++.h>
using namespace std;
int T,M,t[1001],v[1001],dp[1001][1001] = {0};
int solve(int i,int j){
	if(dp[i][j] != 0) return dp[i][j];
    if(i == M) return 0;
    if(j > v[i]) return dp[i][j] = max(solve(i + 1,j),solve(i + 1,j - t[i]) + v[i]);
    else return dp[i][j] = solve(i + 1,j);
} 
int main(){
    cin>>T>>M;
    for(int k = 0 ; k < M ; k++) cin>>t[k]>>v[k];
    cout<<solve(0,T);
    return 0;
}