#include <bits/stdc++.h>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out")
pair<int,int>p[10001];
int main()
{
    int dp[500][10001]={0};///profitul maxim pentru primele i elemente avand greutatea j
    ///raspuns in dp[n][g]
    int n,g,j;
    in>>n>>g;
    for(int i=1;i<=n;i++)
        in>>p[i].first>>p[i].second;
        for(int i=0;i<=n;i++)
            for(j=0;j<=g;j++)
            dp[i][j]=0;
    for(int i=1;i<=n;i++)
        for(j=1;j<=g;j++)
        if(dp[i-1][j]>0 || p[i].first==j || (dp[i-1][j-p[i].first]>0 && j-p[i].first>0))
        dp[i][j]=max(dp[i-1][j],dp[i-1][j-p[i].first]+p[i].second);
    out<<dp[n][g]<<' ';
    return 0;
}