#include<iostream>
using namespace std;
int findM(int N,int K,int G[],int W[])
{    int *M=new int[N+1],i,j,k;   
      for(i=0;i<N+2;i++)
          M[i]=0;
      for(i=0;i<K;i++)
      {        
          for(j=N;j>=G[i];j--)
               {            
                   for(k=1;j-k*G[i]>=0;k++)
                       {
                          M[j]=M[j]>k*W[i]+M[j-k*G[i]]?M[j]:k*W[i]+M[j-k*G[i]];   
                        }    
               } 
       }  
           return M[N];
}
int main(){
        int N,K,i;
        while(cin>>N>>K)
        {
        int *G=new int[K];        
        int *W=new int[K];        
        for(i=0;i<K;i++)       
        cin>>G[i]>>W[i];        
        cout<<findM(N,K,G,W)<<endl;        
        delete []G;       
        delete []W;    
        }    
     return 0;
}

#include<fstream>
#include<iostream>
usingnamespacestd;
#defineMAXSIZE1000
intA[MAXSIZE+1][MAXSIZE+1],B[MAXSIZE+1][MAXSIZE+1];
intc[MAXSIZE+1],w[MAXSIZE+1];
intF(intn,intv){
if(n==0)return0;
if(!A[n][v]&&v>=c[n])
A[n][v]=F(n-1,v-c[n])+w[n];
if(!B[n][v])B[n][v]=F(n-1,v);
returnA[n][v]>B[n][v]?A[n][v]:B[n][v];
}
intmain(intargc,char*argv[])
{
intn,v;
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
ifstreamin("in.txt");
ofstreamout("out.txt");
in>>n>>v;
for(inti=1;i<=n;i++)
in>>c[i]>>w[i];
out<<F(n,v);
return0;
}

var
i,j,v,n:longint;
f,c,w:array[0..100]oflongint;
functionmax(a,b:longint):longint;
begin
ifa>bthenexit(a)elseexit(b);
end;
begin
read(n,v);
fillchar(f,sizeof(f),0);
fori:=1tondo
read(c[i],w[i]);
fori:=1tondo
forj:=vdowntoc[i]do
f[j]:=max(f[j],f[j-c[i]]+w[i]);
writeln(f[v]);
end.

varm,n,x,i:integer;
c,w:array[1..30]ofinteger;
f:array[0..30,0..300]ofinteger;
functionmax(x,y:integer):integer;
begin
ifx>ythenmax:=xelsemax:=y;
end;
begin
readln(n,m);
fori:=1tondo
readln(c[i],w[i]);
fori:=1tondo
forx:=1tomdo
ifx>=c[i]thenf[i,x]:=max(f[i-1,x-c[i]]+w[i],f[i-1,x])
elsef[i,x]:=f[i-1,x];
writeln(f[n,m]);
end.

#include<stdio.h>
#include<malloc.h>
typedefstruct
{
intobject;
intweight;
intvalue;
}KnapSack;
KnapSack*knapsack;//背包数组，用malloc或new动态创建
intnum;//物体的个数
intcontainer;//背包的最大容量
int**array=NULL;//用来存放子问题的结果
//动态创建背包
voidCreate_KnapSack()
{
charc;
printf("inputthenumberofobjects\n");
scanf("%d",&num);
knapsack=newKnapSack[num+1];
printf("inputweightandvalueof%dobjects,like1:410\n",num);
for(inti=1;i<=num;i++)
{
scanf("%d%c%d%c%d",&knapsack[i].object,&c,&knapsack[i].weight,&c,&knapsack[i].value);
getchar();//为了获取空格或其他输入，声明下scanf挺恶心
}
intk=knapsack[num].value;
printf("%d",k);
printf("inputthevolumeoftheknapsack:\n");
scanf("%d",&container);
}
//确定最优子问题
voidResolve_KnapSack()
{
intk=knapsack[num].value;
printf("%d",k);
//创建动态二维数组m[num][container]
array=(int**)malloc((num+1）*sizeof(int*));
for(inti=0;i<=num;i++)
array[i]=(int*)malloc((container+1）*sizeof(int));
//
for(intj=0;j<=container;j++)
array[num][j]=(j>=knapsack[num].weight)?knapsack[num].value:0;
//子问题的最优结果
for(intm=num-1;m>0;m--)
for(intn=0;n<=container;n++)
if(n>knapsack[m].weight&&array[m+1][n]<=array[m+1][n-knapsack[m].weight]+knapsack[m].value)
array[m][n]=array[m+1][n-knapsack[m].weight]+knapsack[m].value;
//else包括两种情况，共同点是该物体没有被使用
else
array[m][n]=array[m+1][n];
}
//往回找，确定某个物体i是否被使用
bool*Trace_back()
{
intc=container;
bool*used;
used=(bool*)malloc(sizeof(bool)*(num+1））；
for(inti=1;i<num;i++)
if(array[i][c]==array[i+1][c])
used[i]=0;
else
{
used[i]=1;
c-=knapsack[i].weight;
}
used[num]=(c==knapsack[num].weight)?1:0;
returnused;
}
//用来输出被使用的物体及其相关值
voidPrint_KnapSack(bool*used)
{
printf("theobjectsusedasfollows:\n");
for(inti=1;i<=num;i++)
if(used[i])
printf("%d:%d%d\n",knapsack[i].object,knapsack[i].weight,knapsack[i].value);
}
voidmain()
{
bool*used;
Create_KnapSack();
Resolve_KnapSack();
used=Trace_back();
Print_KnapSack(used);
}

varp,t:array[1..10000]ofinteger;
m,n:integer;
min:longint;

procedureinit;
vari:integer;
begin
readln(m,n);
min:=maxlongint;
fori:=1tondo
begin
readln(p[i],t[i]);
ift[i]<minthenmin:=t[i];
end;
end;

procedureqsort(l,r:integer);
vari,j,x,temp:longint;
begin
i:=l;
j:=r;
x:=t[(l+r)div2];
whilei<jdo
begin
while(i<j)and(t[i]<x)doinc(i);
while(i<j)and(x<t[j])dodec(j);
ifi<=jthen
begin
temp:=t[i];
t[i]:=t[j];
t[j]:=temp;
temp:=p[i];
p[i]:=p[j];
p[j]:=temp;
inc(i);
dec(j);
end;
end;
ifi<rthenqsort(i,r);
ifl<jthenqsort(l,j);
end;

functionmax(a,b:longint):longint;
begin
ifa>bthenmax:=aelsemax:=b;
end;

procedurework;
varf:array[0..10000]oflongint;
i,j:longint;
begin
fillchar(f,sizeof(f),0);
fori:=mintomdo
begin
f[i]:=f[i-1];
forj:=1tondo
ifi-t[j]>=0thenf[i]:=max(f[i],f[i-t[j]]+p[j])elsebreak;
end;
writeln(f[m]);
end;

begin
init;
qsort(1,n);
work;
end.

var
i,j,v,n:longint;
f,c,w:array[0..100]oflongint;
functionmax(a,b:longint):longint;
begin
ifa>bthenexit(a)elseexit(b);
end;
begin
read(n,v);
fillchar(f,sizeof(f),0);
fori:=1tondo
read(c[i],w[i]);
fori:=1tondo
forj:=c[i]tovdo
f[j]:=max(f[j],f[j-c[i]]+w[i]);
writeln(f[v]);
end.