using namespace std;

const int MAX_N=30000, MAX_M=25;

int v[MAX_M], p[MAX_M];

int f[MAX_N]={0};

int main(){

int n, m;//n总钱数，m物品数量

cin>>n>>m;

for(int i=0;i<m;i++){

cin>>v[i]>>p[i];//v价格，p重要程度

}

/*

分析：

因为每件物品只有一个，所以可化为简单的背包问题：

令f[n]等于钱数为n时最大的乘积和

对于第i件物品来说，有两种情况：

1. 购买(价值为 f[n-v[i]]+v[i]*p[i])

2. 不购买 (价值为 f[n])

整理为状态转移方程：

f[n]=max{f[n],f[n-v[i]]+v[i]*p[i]}

*/

for(int i=0;i<m;i++){

for(int j=n;j>=v[i];j--){

f[j]=(f[j]>f[j-v[i]]+v[i]*p[i])

? f[j]

: f[j-v[i]]+v[i]*p[i];//与状态转移公式f[n]=max{f[n],f[n-v[i]]+v[i]*p[i]}等价

}

}

cout<<f[n];

}