#include <iostream>

using namespace std;
int dp[2][10005], w[5005], p[5005];
int main()
{
    int n, g, k;
    cin >> n >> g;

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

    for(int i = 1;i <= g;i ++)
        dp[0][i] = -1;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 0;j <= g;j ++)
        {
            k = i % 2;
            if(j >= w[i] && dp[1-k][j - w[i]] != -1)
            dp[k][j] = max(dp[1-k][j] , dp[1-k][j - w[i]] + p[i]) ;
            else
            dp[k][j] = dp[1 - k][j];
        }
    }

    int maxi = -1;
    for(int i = 0;i <= g;i ++)
        if(maxi < dp[n%2][i])
            maxi = dp[n%2][i];

    cout << maxi;
    return 0;
}