#include <fstream>
#include <queue>

using namespace std ;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int dp[10010];
int g[5010];
int v[5010];

int main(){
int n,G;
fin>>n>>G;
for( int i=1;i<=n;i++)
fin>>g[i]>>v[i];
for(int j=G-g[i];j>=0;j++)
    if(dp[j]!=0 || j==0)
    dp[j+g[i]]=max(dp[j+g[i]],dp[j]+v[i]);
    int tfisthishit=0;
    for(int i=G;i>=1;i--)
    if(dp[i])tfisthishit=max(tfisthishit,dp[i]);
    fout<<tfisthishit;



    }