#include<stdio.h>
#include<string.h>

int dp[30001],N;

void ZeroOnePack(int c,int w)
{
  for(int i=N;i>=c;i--)
    dp[i]=dp[i]>dp[i-c]+w?dp[i]:dp[i-c]+w;
}

int main()
{
  int m,v[26],p[26];
  while (scanf("%d%d",&N,&m)!=EOF)
  { 
    //读取数据
    for(int i=1;i<=m;i++)
      scanf("%d%d",&v[i],&p[i]);
    //数据初始化 不要求“装满”
    memset(dp,0,sizeof(dp));

    for(int i=1;i<=m;i++)
      ZeroOnePack(v[i],v[i]*p[i]);

    printf("%d\n",dp[N]);
  }
  return 0;
}