include

define MAX 10000

using namespace std;

//int i,j;
int n,m;//n标志背包容量，m标致物品个数
int result=-9999;
int vis[MAX] = {0};
int w[MAX] = {0};
int v[MAX] = {0};

void dfs(int tw,int tv)
{
if(tw>n) return;
for(int i=0;i<m;i++)
{
cout<<"i : "<<m<<endl;

    if(vis[i]==0)
    {
        if(tw+w[i]<=n && tv+v[i]>result) result = tv+v[i];
        vis[i] = 1;
        dfs(tw+w[i], tv+v[i]);
        vis[i] = 0;
    }
}

}
int main()
{
freopen("C://in.txt","r",stdin);
scanf("%d,%d",&n,&m);
for(int j=0;j<m;j++)
{
scanf("%d,%d",&w[j],&v[j]);
}
dfs(0,0);
cout<<result;

}
/*
10,5
2,1
3,2
4,5
5,7
8,9
*/