#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() {
    int n, g;
    scanf("%d %d", &n, &g);

    for(int i = 1; i <= n; i++) {
        scanf("%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];
            }
        }
    }

    printf("%d\n", dp[n][g]);

    return 0;
}