#include

#include <bits/stdc++.h>
using namespace std;
int  n,m,dp[100005],v[1000005],c[1000005],ans=0;

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