#include <bits/stdc++.h>

using namespace std;

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

long long n,g;
long long w[5005],v[5005];
long long dp[10005];

int main(){
    long long i,j,sum=0,answer=-1;

    cin>>n>>g;

    for(i=1;i<=n;i++)
        cin>>w[i]>>v[i];

    dp[0]=0;

    for(i=1;i<=n;i++){
        sum+=w[i];
        for(j=sum;j>=w[i];j--)
            dp[j]=max(dp[j],v[i]+dp[j-w[i]]);
    }

    for(i=1;i<=g;i++)
        if(dp[i]>answer)
            answer=dp[i];

    cout<<answer;

    return 0;
}