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

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

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;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= gmax; ++j){
            dp[i&1][j] = dp[(i - 1)&1][j];
            if(v[i].G <= j)
                dp[i&1][j] = max(dp[i&1][j], dp[(i-1)&1][j-v[i].G]+v[i].V);
        }
    }
    cout << dp[n&1][gmax];
}