#include <bits/stdc++.h>

using namespace std;

const int N = 5005;
const int G = 10005;

int W[N],P[N],dp[G];

int main() {
    int i,j,n,g;
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d %d",&n,&g);
    for(i = 1;i <= n;i++){
        scanf("%d %d",&W[i],&P[i]);
    }
    for(i = 1;i <= n;i++){
        for(j = g;j >= W[i];j--){
            dp[j] = max(dp[j],dp[j - W[i]] + P[i]);
        }
    }
    printf("%d",dp[g]);
    return 0;
}