#include <bits/stdc++.h>

using namespace std;

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

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

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

    fin>>n>>g;

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

    dp[0]=0;

    for(i=1;i<=n;i++){
        for(j=g;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];

    fout<<answer;

    return 0;
}