#include <bits/stdc++.h>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

struct object{
    int val, wt;
} v[10001];

int n, W;

int KnapSack(int n, int W){

    int mat[2][W + 1];
    memset(mat, 0, sizeof(mat));

    int i = 1, x = 0, y = 1;
    while(i <= n){

        int j = 0;

        while(++j <= W){

            if(v[i].wt <= j) mat[y][j] = max(v[i].val + mat[x][j - v[i].wt], mat[x][j]);
            else mat[y][j] = mat[x][j];
        }
        i++, x ^= 1, y ^= 1;
    }

    return mat[x][W];
}

int main(){

    f >> n >> W;
    for(int i = 1;i <= n;i++)
        f >> v[i].wt >> v[i].val;

    g << KnapSack(n, W);
}