#include <iostream>
#include <cstring>
using namespace std;
const int N=10000+10;
int t,m;
int a[N],b[N];
int ans=-2e8;
void dfs(int u,int t1,int money){
    if (t1>t) return; // 超时
    if (u==m+1) {// 遍历完所有草药，更新答案
        ans=max(ans,money);
        return;
    }
    for (int i=0; i*a[u]<=t;i++){ // 枚举采摘当前草药的数量
        dfs(u+1,t1+i*a[u],money+i*b[u]);
	}
}
int main(){
    cin>>t>>m;
    for (int i=1;i<=m;i++)
		cin>>a[i]>>b[i];
    dfs(1,0,0);
    cout<<ans<<endl;
    return 0;
}