#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;

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


int n, G;

struct item {
    int w;
    int p;
};

item v[5005];
bool possible[10005];
int sum[10005];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    fin >> n >> G;
    for (int i = 1; i <= n; i++) {
        fin >> v[i].w >> v[i].p;
    }

    int maxProfit = 0;
    possible[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = G - v[i].w; j >= 0; j--) {
            if (possible[j] && sum[j + v[i].w] < sum[j] + v[i].p) {
                sum[j + v[i].w] = sum[j] + v[i].p;
                possible[j + v[i].w] = 1;
            }
        }
    }

    for (int i = G; i >= 0; i--) {
        if (sum[i] >= maxProfit) {
            maxProfit = sum[i];
        }
    }

    fout << maxProfit << "\n";

    return 0;
}