i,j,m,n:longint;
g:array[0..30000] of longint;w,v:array[1..25] of longint;
begin
readln(n,m);for i:=1 to m do read(v[i],w[i]);
for i:=1 to m do
for j:=n downto v[i] do
if g[j]<g[j-v[i]]+v[i]*w[i] then
g[j]:=g[j-v[i]]+v[i]*w[i];
writeln(g[n]);
end.
int main()
{
int v[30],p[30],sum[300000];
int m,n,i,j;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++)
{
scanf("%d%d",&v[i],&p[i]);
}
for (i=1;i<=m;i++)
{
for (j=n;j>=v[i];j--)
{
if (sum[j]<sum[j-v[i]]+v[i]*p[i])
sum[j]=sum[j-v[i]]+v[i]*p[i];
}
}
printf("%d\n",sum[n]);
return 0;
}
#include<limits.h> //别写错了是limits.h
//1.状态：i即横坐标表示价格v，j即纵坐标表示第i个物品，a[i][j]表示在价格为i时可以装的最多收益
//2.决策：a[i][j]=max(a[i-v[j]][j-1]+w[j],a[i][j-1])
//3.初始状态： 结束状态：answer=a[m][m]
//4.收益：v[i]*w[i]
//5.无后效性：满足
int a[30005][30];
int v[30],w[30];
int n,m,i,j,minv=INT_MAX,k,ans;
int main(){
scanf("%d%d",&n,&m); //总价钱n，物品总数m
for(i=1;i<=m;i++){
scanf("%d%d",&v[i],&w[i]);
if(v[i]<minv) minv=v[i];
}
for(i=0;i<=n+1;i++){
for(j=0;j<=m+1;j++){
a[i][j]=0;
}
}
for(j=1;j<=m;j++){
for(i=n;i>=0;i--){
if(v[j]>i) a[i][j]=a[i][j-1];
else a[i][j]=a[i-v[j]][j-1]+w[j]*v[j]>a[i][j-1]?a[i-v[j]][j-1]+w[j]*v[j]:a[i][j-1];
}
}
/*for(i=minv;i<=n;i++){
for(j=1;j<=m;j++){
printf("%d ",a[i][j]);
}
printf("\n");
}*/
ans=a[n][m];
/*for(k=n;k>=0;k--){
if(a[k][m]==a[k-1][m]) continue;
else {
printf("a[n][m]=%d\n",a[n][m]);
printf("k=%d\n",k);
ans=ans*k;
break;
}
}*/
//printf("ans=");
printf("%d\n",ans);
}