#include<bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int mat[5005][10005];
int main(){
int n,g,i,j;
in>>n>>g;
int vet[n],profit[n];
for(i=0;i<n;i++)
in>>vet[i]>>profit[i];

for(j=vet[i];j<=g;j++){
    if(mat[i-1][j]>mat[i-1][j-vet[i]]+profit[i])
    mat[i][j]=mat[i-1][j];
    else mat[i][j]=mat[i-1][j-vet[i]]+profit[i];

}
out<<mat[n-1][g];
}