#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>

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

struct set
{
    int w, p;
};

set vec[1000];
int n, g;
set aux;


int main()
{
    fin >> n >> g;
    for (int i = 1; i <= n; i++)
    {
        fin >> vec[i].w >> vec[i].p;
    }
    int arr[n + 1][g + 1];
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < g; j++){
            arr[i][j] = 0;
        }
    }

    //cout << "\n";
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= g; j++){
            if(j < vec[i].w || arr[i - 1][j] >= arr[i - 1][j - vec[i].w] + vec[i].p){
                arr[i][j] = arr[i - 1][j];
            } else {
                arr[i][j] = arr[i - 1][j - vec[i].w] + vec[i].p;
            }       
        }
    }
    

    //for(int i = 1; i <= n; i++){
    //    for(int j = 1; j <= g; j++){
    //        cout << arr[i][j] << " ";
    //    }
        fout << arr[n][g] << "\n";
    //}

return 0;
}