#include<iostream>
#include<algorithm>
using namespace std;
const int N = 25;
int value[N],weigth[N];
int OPT(int total,int num){
if(total < value[num]){
if(num>0){//当我们买不起的时候,我们没得选,只能移向下一个物品
return OPT(total,num-1);
}else{
return 0;
}
}
if(num ==0){//当我们能买当前物品,但该物品已经是最后一个了,我们就不需要考虑状态转移方程了
return weigth[num]*value[num];
}
if(total>=value[num]){// 我们从最后一个物品开始考虑,有选和不选两种选项
int A=OPT(total-value[num],num-1)+weigth[num]*value[num];//我们总的金钱需要能够买得起该物品,当我们选择买,状态就变成了
int B=OPT(total,num-1);//当我们买不起的时候,我们没得选,只能移向下一个物品
return A>B?A:B;
}
}
int main(){
int total,num;
cin>>total>>num;
for(int i=0;i<num;i++){
cin>>value[i]>>weigth[i];
}
cout<<OPT(total,num-1);
return 0;
}