#include <iostream>

using namespace std;

void fast_io()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
}

int main()
{
    fast_io();
    int m, n;
    cin >> n >> m;
    int p[n+1] = {0};
    int w[n+1] = {0};
    int v[n+1][m+1];

    for (int i = 1; i < n+1; i++){
        cin >> w[i] >> p[i];
    }

    for (int i = 0; i < n+1; i++){
        for (int j = 0; j < m+1; j++){
            v[i][j] = 0;
        }
    }

    for (int i = 1; i < n+1; i++){
        for (int j = 1; j < m+1; j++){
            if (j-w[i] >= 0){
                v[i][j] = max(v[i-1][j], v[i-1][j-w[i]]+p[i]);
            }else{
                v[i][j] = v[i-1][j];
            }
        }
    }
    int num = v[n][m];
    int results[n+1] = {0};
    for (int i = n; i >= 1; i--){
        for (int j = m; j >= 1; j--){
            if (v[i-1][j] == num){
                break;
            }
            if (j == 1){
                num -= p[i];
                results[i] = 1;
            }
        }
    }
    int sum = 0;
    for (int i = 0; i < n+1; i++){
        if (results[i] == 0){continue;}
        sum += p[i];
    }
    cout << sum << endl;
}