// #include <cmath>
// #include <cstdio>
// #include <vector>
// #include <iostream>
// #include <algorithm>
// using namespace std;

// int w[10005];
// int p[10005];
// int dp[10005][10005];

// int main() {
//     FILE *fin = fopen("rucsac.in", "r");
//     FILE *fout = fopen("rucsac.out", "w");

//     int n, g;
//     fscanf(fin, "%d %d", &n, &g);

//     for(int i = 1; i <= n; i++) {
//         fscanf(fin, "%d %d", &w[i], &p[i]);
//     }

  
//     for(int i = 1; i <= n; i++) {
//         for(int j = 1; j <= g; j++) {
//             if(w[i] <= j) {
//                 dp[i][j] = max(dp[i-1][j], p[i] + dp[i-1][j - w[i]]);
//             } else {
//                 dp[i][j] = dp[i-1][j];
//             }
//         }
//     }

//     fprintf(fout, "%d\n", dp[n][g]);

//     return 0;
// }


#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int w[10005];
int p[10005];
int cur[10005];
int vechi[10005];


int main() {
    FILE *fin = fopen("rucsac.in", "r");
    FILE *fout = fopen("rucsac.out", "w");

    int n, g;
    fscanf(fin, "%d %d", &n, &g);

    for(int i = 1; i <= n; i++) {
        fscanf(fin, "%d %d", &w[i], &p[i]);
    }

  
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= g; j++) {
            if(w[i] <= j) {
                cur[j] = max(vechi[j], p[i] + vechi[j - w[i]]);
            } else {
                cur[j] = vechi[j];
            }
        }
        for (int k = 1; k <= g; k++) {
            vechi[k] = cur[k];
        }
    
    }

    fprintf(fout, "%d\n", cur[g]);

    return 0;
}