#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int m1[10005][10005];
struct ada{
    int wt,val;
}v1[5000];


int main()
{
    int n,g,x,y,m;
    fin>>n>>g;
    for(int i=0;i<n;i++){
        fin>>x>>y;
        v1[i].wt = x;
        v1[i].val = y;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=g;j++){
            if(j>=v1[i].wt && i==0)
                m1[i][j] = v1[i].val;
            else {
                if(j<v1[i].wt && i!=0)
                    m1[i][j] = m1[i-1][j];
                if(j>=v1[i].wt && i!=0)
                    m1[i][j] = max(m1[i-1][j],v1[i].val + m1[i-1][j-v1[i].wt]);
            }
        }
    }
    fout<<m1[n-1][g];
    return 0;
}