//Problema Knapsack - Varianta Bottom-Up
#include <fstream>
#include <cmath>

using namespace std;

ifstream cin("rucsac.in");
ofstream cout("rucsac.out");

const int MAX_N = 5001;
const int MAX_G = 10001;

//dp[idx][capacitate] // fiind global, toate valorile matricei sunt initializate cu 0;
int dp[MAX_N][MAX_G];

int nr_elem, gMax;

struct t_object{
    int weight;
    int profit;
};

int main(){

    t_object objs[MAX_N];

    cin >> nr_elem >> gMax;

    for(int i = 1; i <= nr_elem; i++){
        int greutate;
        int profit;

        cin >> greutate >> profit;

        t_object obiect = {greutate, profit};

        objs[i] = obiect;
    }

    //cazul idx == 0 deja rezolvat, la fel si pentru greutate == 0;
    for(int idx = 1; idx <= nr_elem; idx++){
        for(int capacitate = 1; capacitate <= gMax; capacitate++){
            t_object obj_curr = objs[idx];

            if(obj_curr.weight > capacitate)
                    //nu are loc in ghiozdan
                    dp[idx][capacitate] = dp[idx - 1][capacitate];
            else{
                //nu punem obiectul in ghiozdan
                int profit1 = dp[idx - 1][capacitate];

                //punem obiectul in ghiozdan
                int profit2 = obj_curr.profit + dp[idx - 1][capacitate - obj_curr.weight];

                dp[idx][capacitate] = max(profit1, profit2);
            }
        }
    }

    cout << dp[nr_elem][gMax];

    return 0;
}