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



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

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

    for (int i = 0; i < n; i++)
        cin >> 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]);

    cout << dp[W];
}