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


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


int knapsack(int W, vector <short int> &wt, vector <short int> &val, int n)
{
    vector <vector <short int>> dp (n + 1, vector <short int> (W + 1, 0));

    for (int i = 1 ; i <= n; i++)
        for (int w = 1; w <= W; w++)
            if (wt[i - 1] <= w)
                dp[i][w] = (short int) max(dp[i - 1][w], (short int)(dp[i - 1][w - wt[i - 1]] + val[i - 1]));
            else
                dp[i][w] = dp[i - 1][w];


    return dp[n][W];
}

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

    vector <short int> val (n);
    vector <short int> wt (n);

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


    fout << knapsack(W, wt, val, n);
}