#include <bits/stdc++.h>
using namespace std;


ifstream fin("rucsac.in");
ofstream fout("rucsac.out");


int main()
{
    int n, W;
    fin >> n >> W;

    int val[n];
    int wt [n];

    for (int i = 0; i < n; i++)
        fin >> wt[i] >> val[i];


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

    for (int i = 0; i < n; i++)
        for (int w = W; w >= wt[i]; w--)
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

    fout << dp[W];
}