#include <bits/stdc++.h>
using namespace std;

long long c[10002][10002];
long long a[10002];
long long b[10002];

int main(){
	
	long long t;
	long long m;
	
	cin>>t>>m;
	
	for(long long i = 1 ; i<=m ;i++){
		
		long long p,q;
		
		cin>>p>>q;
		
		a[i]=p;
		
		b[i]=q;
		
	}
	
	for(long long i = 1; i<=m;i++){
		
		for(long long j =1; j<=t;j++){
			
			if(j<a[i]){
				
				c[i][j]=c[i-1][j];
				
			}else{
					
					c[i][j]=max(c[i-1][j],c[i][j-a[i]]+b[i]);
					
				}
				
			}
			
		}
		
		cout<<c[m][t]<<endl;
		
	}