#include <bits/stdc++.h>

using namespace std;
int N,M,v[30],w[30],answer;
int vis[30][30010];
void input()
{
    cin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        scanf("%d%d",&v[i],&w[i]);
        w[i]*=v[i];
    }
    for(int i=1;i<=M;i++)
        for(int j=1;j<=N;j++)
            vis[i][j]=-1;
}
int work(int now,int Time)
{
    int ans=0;
    if(Time==0)
    {
        return 0;
    }
    if(vis[now][Time]!=-1)
    {
        return vis[now][Time];
    }
    ans=work(now-1,Time);
    if(Time>=v[now])
    {
        ans=max(ans,work(now-1,Time-v[now])+w[now]);
    }
    vis[now][Time]=ans;
    return ans;
}
void output()
{
    cout<<answer;
}
int main()
{
    input();
    answer=work(N,M);
    output();
    return 0;
}