#include <cstdio>
#include <algorithm>
#define Mx 5001
#define Gx 10001
using namespace std;
int N, G, w[Mx], p[Mx], dp[Gx];
int main(){
    freopen("rucsac.in", "r", stdin);
    freopen("rucsac.out", "w", stdout);
    scanf("%d%d", &N, &G);
    for(int i = 0; i < N; i++) scanf("%d%d", &w[i], &p[i]);
    dp[0] = 0;
    for(int i = 0; i < N; i++){
        for(int j = G; j >= w[i]; j--){
            dp[j] = max(dp[j], dp[j - w[i]] + p[i]);
        }
    }
    printf("%d", dp[G]);
    return 0;
}