///

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int n,k;
vector<pair<int,int>>obj; ///vectorul care memoreaza valoarea si greutatea
///fiecarui obiect intr-o structura de forma pair- prima este greutatea,
///a doua este profitul
vector<vector<int>>dp;  ///matrice de tip vector care retine la pozitia
///(i,j) valoarea maxima atunci cand sunt alese cel mult i din primele obiecte,
///care ocupa o masa j
///profitul maxim pe care-l putem obtine selectand o submultime a primelor i
///elemente, a caror greutate insumata este egala cu cw


int main(){
    ifstream f("knapsack.in");
    ofstream g("knapsack.out");

    f>>n; ///citim numarul de obiecte
    obj.resize(n+1);
    f>>k; ///citim capacitatea rucsacului
    dp.resize(n+1, vector<int>(k+1));


    for (int i = 1; i <= n; i ++) f >>obj[i].first>>obj[i].second;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= k; j++){
            if (obj[i].first <= j)
                dp[i][j] = max (dp[i-1][j], dp[i-1][j - obj[i].first] + obj[i].second);
                else dp[i][j] = dp[i-1][j];
        }

    g << dp[n][k]; ///pozitia (n,k) din matrice va reprezenta profitul maxim,
///intrucat este pozitia pe care se pot folosi cat mai multe obiecte cu maximul
///de greutate fiind chiar capacitatea rucsacului

    return 0;
}