#include <bits/stdc++.h>
#define G first
#define V second
using namespace std;

int n,gmax, um[10005][10005];
pair<int, int> v[5005];

int rec(int i, int g){
    if(g < 0)return INT_MIN;
    if(!g || i < 2)return um[i][g] = 0;
    return um[i][g] = max(rec(i - 1, g - v[i - 1].G) + v[i - 1].V, rec(i - 1, g));
}


int main(){
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
    cin >> n >> gmax;
    for(int i = 1; i <= n; ++i)
        cin >> v[i].G >> v[i].V;
    cout << rec(n + 1, gmax);
}