#include <bits/stdc++.h>

using namespace std;
ifstream in  ("rucsac.in");
ofstream out("rucsac.out");

#define maxG 10000

int v[2][maxG+1];

int main(){
	int n,G;
	cin>>n>>G;
	for(int i=1;i<=n;i++){
        int g,p;
		cin>>g>>p;
		for(int j=0;j<=G;j++){
			v[i&1][j]=v[(i-1)&1][j];
            if(g<=j){
				v[i&1][j]=max(v[(i-1)&1][j],v[(i-1)&1][j-g]+p);
            }
		}
	}
	cout<<v[(n&1)][G];
}