#include <bits/stdc++.h>
using namespace std;

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

int n, G;
int w[5005], p[5005], dp[10005];

int main()
{
    int i, j;
    fin >> n >> G;
    for (i = 1; i <= n; i++)
        fin >> w[i] >> p[i];

    for (i = 1; i <= n; i++)
        for (j = G - w[i]; j >= 0; j--)
            if (dp[j] != 0 || j == 0)
                dp[j + w[i]] = max(dp[j + w[i]], dp[j] + p[i]);
    int Max = -1;
    for (i = 1; i <= G; i++)
        Max = max(Max, dp[i]);
    fout << Max << "\n";
    return 0;
}