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

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

int rezolvare(int indice, int greutate, vector<vector<int>> &dp,
              vector<int> &greutati, vector<int> &profit)
{
    if (indice==0 ||greutate==0)
        return 0;

    if (dp[indice][greutate] != -1)
        return dp[indice][greutate];

    int notake=rezolvare(indice-1, greutate, dp, greutati, profit);
    int take=INT_MIN;

    if (greutati[indice - 1] <= greutate)
        take= profit[indice - 1] + rezolvare(indice-1,greutate-greutati[indice - 1],dp,greutati,profit);

    return dp[indice][greutate] = max(notake, take);
}

int main()
{
    int n, gr;
    fin>>n>>gr;
    vector<vector<int>> dp(n + 1, vector<int>(gr + 1, -1));
    vector<int> profit(n);
    vector<int> greutati(n);

    for (int i=0; i<n; i++)
        fin>>greutati[i]>>profit[i];

    fout<<rezolvare(n,gr,dp,greutati,profit) << endl;
    return 0;
}