#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;
}