#include<bits/stdc++.h>
using namespace std;
int a[1010][1050];
//int k(int c,int n){
//	if(n == 0&&c == 0){
//		return 0;
//	}
//	
//	if(c<w[i]){
//		return k(c,n-1);
//	}
//	else{
//		return max(k(c-v[i],n-1)+w[i] , k(c,n-1));
//	}
//}

int main(){
	int n,m;
	cin>>n>>m;
	int v[10010],w[10010];
	for(int i = 1;i<=m;i++){
		cin>>v[i]>>w[i];
	}
	//对记录问题（即状态）的二维数组a[i][j]（记录的是价值）进行填充 
	for(int i = 1;i<=n;i++){
		for(int j = 0;j<=m;j++){
			//当前背包容量j能不能装下第i个物品 
			//如果不能装入（即背包容量小于第i个物品的体积 
			if(j < v[i]){
				a[i][j] = a[i-1][j];
			}
			//能够装入 
			else{
				a[i][j] = max(a[i-1][j-v[i]]+w[i],a[i-1][j]);
			}
		}
	}
	cout<<a[n][m];
	return 0;
}