#include <string.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int knapsack(const vector<int>& g, const vector<int>& p, int G) {
    vector<int> pMax(G + 1, 0);
    int pMaxValue = INT_MIN + 1;
    pMax[g[0]] = p[0];
    for (int i = 1; i< g.size(); i++) {
        for (int w = G; w > g[i]; --w) {
            if (w != 0 && pMax[w - g[i]] != 0) { 
                pMax[w] = max(pMax[w - g[i]] + p[i], pMax[w]);
            }
        }
        pMax[g[i]] = max(pMax[g[i]], p[i]);
        std::cout << "\t-----\n";
        for (int i = 0; i <= G; i++) {
            std::cout << pMax[i] << " ";
        }
        std::cout << "\n";
    }

    for (int i = 0; i <= G; i++) {
        pMaxValue = max(pMaxValue, pMax[i]); 
    }
    
    return pMaxValue;
}

int main() {
    int n, G;
    freopen("rucsac.in", "r", stdin);
    //freopen("rucsac.out", "w", stdout);
    scanf("%d %d", &n, &G);
    vector<int> g(n);
    vector<int> p(n);
    
    for (int i = 0; i < n; ++i) {
        scanf("%d %d", &g[i], &p[i]);
    }      

    for (int i = 0; i < n; ++i) {
        std::cout << g[i] << " " << p[i] << "\n";
    }      


    printf("%d", knapsack(g, p, G));
    return 0;
}