#include <fstream>
#include <algorithm>
#include <vector>
#define dim 4002
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

int n,g,prf;
int w[5002],v[5002];
vector<int>V[10002];

int main()
{
    cin>>n>>g;
    for(int i=1;i<=n;++i)
        cin>>w[i]>>v[i];
        
    for(int i=0;i<=n;++i)
        for(int j=0;j<=g;++j)
            if(i==0 || j==0) V[i].push_back(0);
            else if(w[i]<=j)
                V[i].push_back(max(v[i]+V[i-1][j-w[i]],V[i-1][j]));
            else V[i].push_back(V[i-1][j]);
    
    int i=n,j=g;
    while(i>0 && j>0)
        if(V[i][j]==V[i-1][j]) i--;
        else prf+=v[i],j-=w[i--];
    
    cout<<prf;
    return 0;
}