#include <bits/stdc++.h>
using namespace std;
struct shopping {
int price,important,value;
}a[1000000];
int f[1000000];
int main(){
	freopen("happy.in","r",stdin);
	freopen("happy.out","w",stdout);
    int high,n;
    cin>>high>>n;
    for(int i=1; i<=n; i++) {
        cin>>a[i].price>>a[i].important;
        a[i].value=a[i].important*a[i].price;
    }
    for(int i=1; i<=n; i++)         
        for(int j=high; j>=a[i].price; j--)
            f[j]=max(f[j],f[j-a[i].price]+a[i].value);
	cout<<f[high];
    return 0;
}