#include

#include <bits/stdc++.h>
using namespace std;
int  n,m,dp[1005][1005],v[1005],c[1005],ans=0;
//完全背包
//
//物品无限
//
//状态转移方程式：dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+c[i]); 

int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>v[i]>>c[i];
	}
	for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(j>=v[i]){
                dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+c[i]); 
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout<<dp[n][m];
	return 0;
}