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

using namespace std;

struct object{
    int weight, price;
};

int main() {
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    int noObjects, maxWeight;

    f>>noObjects>>maxWeight;
    vector<object> objects(noObjects+1);
    for(int i=1; i<=noObjects; i++){
        f>>objects[i].weight>>objects[i].price;
    }

    for(int i=1; i<=noObjects; i++){
        cout<<objects[i].weight<<" "<<objects[i].price<<endl;
    }

    vector<int> pricesPerWeight(maxWeight+1);
    int maxPrice=0;
    for(int i=1; i<=noObjects; i++){
        for(int j=maxWeight; j>=objects[i].weight; j--){
            if(pricesPerWeight[j-objects[i].weight]>0 || j==objects[i].weight){
                pricesPerWeight[j]=max(pricesPerWeight[j], pricesPerWeight[j-objects[i].weight]+objects[i].price);
                if(pricesPerWeight[j]>maxPrice) maxPrice=pricesPerWeight[j];
            }
        }
    }

    g<<maxPrice<<endl;

    return 0;
}