0-1背包
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f
void print(int a[],int n){
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
}
void solve()
{
}
int dp[30010];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int m,n;
cin>>m>>n;
for(int i=1;i<=n;i++){
int v,p;
cin>>v>>p;
for(int j=m;j>=v;j--)
dp[j]=max(dp[j],dp[j-v]+v*p);
}
cout<<dp[m]<<endl;
return 0;
}