#include<bits/stdc++.h>
using namespace std;
// [1] Node结构体：存储每个物品的重量w和价值p；arr数组：存储所有物品的信息
struct Node{
	int w,p;
}arr[200];
// [2] dp数组：动态规划数组，dp[j]表示背包容量为j时能装的最大价值
int dp[20100]={};

int main(){
    int maxw,n; // [3] maxw：背包的最大载重；n：物品的总数
	cin>>maxw>>n; // [4] 读取背包最大载重和物品数量
	// [5] 读取每个物品的重量和价值，存入arr数组
	for(int i=0;i<n;i++) cin>>arr[i].w>>arr[i].p;
	
	// [6] 0-1背包核心逻辑：遍历每个物品，更新不同容量下的最大价值
	for(int i=0;i<n;i++){// 外层循环：遍历每个物品
		// 内层循环：逆序遍历背包容量，避免同一个物品被重复选取（0-1背包特性）
		for(int j=maxw;j>=arr[i].w;j--){// 对容量从大到小讨论
			// 递推式：容量j时的最大价值 = max(不选当前物品的原有值, 选当前物品后的值)
			dp[j]=max(dp[j],dp[j-arr[i].w]+arr[i].p);
		}
	}
	
	// [7] 输出背包最大容量maxw下的最大价值
	cout<<dp[maxw];
    return 0;
}