#include <fstream>
#include <queue>

using namespace std ;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");
int g[5010];
int v[5010];
int dp[10010];
int main(){
int n,G;int i,j;
fin>>n>>G;
for( i=1;i<=n;i++)
fin>>g[i]>>v[i];
for(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(i=G;i>=1;i--)
    if(dp[i])tfisthishit=max(tfisthishit, dp[i]);
    fout<<tfisthishit;



    }