#include <stdio.h>
#define MAX 30001
//--------------------------
int main(void)
{
//========================================================
// du qu yao gou mai de zong jia yi ji wu pin shu liang.==
int N, m;
scanf("%d %d", &N, &m);
//========================================================
// wu pin dan jia shu zu; wu pin zhong yao du shu zu;
// zai gai zong jia xia de cheng ji zhi he shu zu.========
int v[m], w[m];
int dp[MAX] = {0};
int i;
for (i = 0; i < m; i++) {
scanf("%d %d", &v[i], &w[i]);
}
//========================================================
// ji suan mei ge zong jia xia de zui da cheng ji zhi he.=
int j;
for (i = 0; i < m; i++) {
for (j = N; j >= v[i]; j--)
dp[j] = dp[j] > (dp[j-v[i]] + v[i]*w[i]) ? dp[j] : (dp[j-v[i]] + v[i]*w[i]);
}
//========================================================
// shu chu gei ding zong jia de zui da cheng ji zhi he.===
printf("%d\n", dp[N]);
return 0;
}
#include <iostream>
#define MAX 30001
using namespace std;
//--------------------------
int main(void)
{
//========================================================
// du qu yao gou mai de zong jia yi ji wu pin shu liang.==
int N, m;
cin>>N >>m;
//========================================================
// wu pin dan jia shu zu; wu pin zhong yao du shu zu;
// zai gai zong jia xia de cheng ji zhi he shu zu.========
int v[m], w[m];
int dp[MAX] = {0};
int i;
for (i = 0; i < m; i++) {
cin>>v[i] >>w[i];
}
//========================================================
// ji suan mei ge zong jia xia de zui da cheng ji zhi he.=
int j;
for (i = 0; i < m; i++) {
for (j = N; j >= v[i]; j--)
dp[j] = dp[j] > (dp[j-v[i]] + v[i]*w[i]) ? dp[j] : (dp[j-v[i]] + v[i]*w[i]);
}
//========================================================
// shu chu gei ding zong jia de zui da cheng ji zhi he.===
cout<< dp[N]<< endl;
return 0;
}