#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;

ifstream f ("rucsac.in");
ofstream g ("rucsac.out");
int n, m;
int w[10001], p[10001];
int v1[10001], v2[10001];

int main() {
    in >> m >> n;
    for (int i = 1; i <= m; i++)
        in >> w[i] >> p[i];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if(i % 2) {
                if (w[i] <= j)
                    v1[j] = max(p[i] + v2[j - w[i]], v2[j]);
                else
                    v1[j] = max(v1[j - 1], v2[j]);
            } else {
                if (w[i] <= j)
                    v2[j] = max(p[i] + v1[j - w[i]], v1[j]);
                else
                    v2[j] = max(v2[j - 1], v1[j]);
            }
        }
    }

    if (m % 2)
        out << v1[n];
    else
        out << v2[n];
}