#include<iostream>
using namespace std;

//比较两个数的大小，返回较大的数
int max(int a,int b)
{
    if(a >= b)
        return a;
    else
        return b;
}

//01背包动态规划算法
//C:背包总的容积
//n：物品总数量
//w[]: 存n个物品的重量,  v[]:保存n个物品的价值
int KnapSack(int C, int n, int w[], int v[]){
	
	//因为要求 vw[n][C]的值，所以要定义 大小为vw[n+1][C+1]的数组 
	int vw[n+1][C+1];//容量为C的背包，放n个商品 的最大价值
	
	//定义边界值：背包容量为0时，无法放入商品，所以价值为0
	for(int i=0;i<=n;i++){
		vw[i][0]=0;
	} 
	
	//定义边界值：无商品时，无论背包容积多大，价值为0
	for(int j = 0; j <= C; j++)
    {
        vw[0][j] = 0;
    }
    
    //从只放1件商品开始，一直到N件商品 
    for(int i = 1; i <= n; i++)
    {
    	//背包容量从1开始，到最大容量C 
        for(int j = 1; j <= C; j++)
        {
        	//背包目前的容量小于 第i件商品的重量 ，说明第i件商品放
			//不进去 
            if(j < w[i])
                vw[i][j] = vw[i-1][j];
            else
                vw[i][j] = max(vw[i-1][j], vw[i-1][j-w[i]]+v[i]);
        }
    }
    
     //定义数组，x[1]=0:表示没有装入第一件商品
	 // x[1]=1：表示装入第1件商品： 
    int x[n+1];
    int j = C;
    for(int i = n ; i >= 0; i--)
    {
    	//表示装入第i件商品后 (装入i物品比不装i物品价值大)
        if(vw[i][j] > vw[i-1][j])
        {
            x[i] = 1;//说明包里面装了i物品
            j = j - w[i];//把i物品去掉
            
            
        }
        else
            x[i] = 0;      
    }

    
    return vw[n][C];	 
}

int main(){
	
	int n;//物品数量 <100
	int c;//背包容量
	cin>>c;
	cin>>n;
	
	int v[100];//保存n个物品的价值
	int w[100];// 保存n个物品的重量
	
	//因为下标代表个数，所以从1开始 
	
	for(int i=1;i<=n;i++){
		cin>>w[i];
		cin>>v[i];
	} 

	
	cout<<KnapSack(c,n,w,v)<<endl;
}

/**************************************************************
	Problem: 1282
	User: admin
	Language: C++
	Result: Accepted
	Time:74 ms
	Memory:9212 kb
****************************************************************/