#include<cstdio>
//#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> v;
int n,w,W,V,L,R,low=-100000000;
int main()
{
    freopen("rucsac.in","r",stdin);freopen("rucsac.out","w",stdout);scanf("%d%d",&W,&V);v.assign(w+1,low);v[0]=0;
    for(;n;n--){scanf("%d%d",&W,&V);R=L=w;L-=W;for(;L+1;R--,L--)v[R]=max(v[R],v[L]+V);}
    for(R=1,V=0;R<=w;R++)V=max(V,v[R]);printf("%d\n",V);return 0;
}