#include <iostream>
#include <fstream>
#include <queue>
#include <string.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#define for0(i,n) for(int i=0; i<n; i++)
#define for1(i,n) for(int i=1; i<=n; i++)
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define V vector<int>
#define VP vector<pair<int, int> >
#define clr(A,x) memset(A, x, sizeof(A))
#define cpy(A,B) memcpy(A, B, sizeof(B))
#define g(s) getline(cin, s) ///ai grija la fin ///
#define FASTIO ios_base::sync_with_stdio(0)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MAX=100005;
const ull MOD=100003;
const int NR_CIFRE=100005;
/*template <typename T>
string to_string(const T& n){
    ostringstream os;
    os << n;
    return os.str();
}
*/
/*struct coord
{
    int x,y;

};
bool operator<(const coord &l, const coord &r)
{
    return (l.x<r.x || (l.x==r.x && l.y<r.y));
}*/

ifstream fin("rucsac.in"); /// modifica cu numele corespunzator
ofstream fout("rucsac.out"); /// modifica cu numele corespunzator

int v[3][10001];

int main()
{
    //VP v;
    int n, g;
    fin>>n>>g;
    for1(o, n)
    {
        int w,p;
        fin>>w>>p;
        for0(i,g+1)
        {
            if(i>=w)
            {
                if(p+v[1][i-w]>v[1][i])
                    v[2][i]=p+v[1][i-w];
                else v[2][i]=v[1][i];
            }
            else v[2][i]=0;
        }
        for0(i,g+1)
        {
            v[1][i]=v[2][i];
            v[2][i]=0;
        }
    }
    fout<<v[1][g];


    return 0;
}