//01背包问题

#include <iostream>

using namespace std;

int a , b;
const int N = 10010;
int v[N],w[N];
int dp[N][N];

int main(){
    cin >> a >> b;
    for (int i = 1; i <= a; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= a; i ++ ) {
        for (int j = 0; j <= b; j ++ ) {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i]) {
                dp[i][j] = max(dp[i][j],dp[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    cout << dp[a][b] << endl;
}

// #include <iostream>

// using namespace std;

// int a,b;
// const int N = 10100;
// int w[N],v[N],dp[N];

// int main(){
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);
//     cout.tie(nullptr);
//     cin >> a >> b;
//     for (int i = 1; i <= a; i ++ ) cin >> v[i] >> w[i];
//     for (int i = 1; i <= a; i ++ ) {
//         for (int j = b; j >= v[i]; j -- ){
//             dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
//         }
//     }
//     cout << dp[b] << endl;
// }

//完全背包问题

#include <iostream>

using namespace std;

int a,b;
const int N = 101001;
int v[N],w[N],dp[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> a >> b;
    for (int i = 1; i <= a; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= a; i ++ ) {
        for (int j = v[i]; j <= b; j ++ ) {
            dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[b] << endl;
}

#include <iostream>

using namespace std;

int a,b;
const int N = 10010;
int w[N],v[N],dp[N][N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> a >> b;
    for(int i = 1; i <= a; i ++ ) cin >> v[i] >> w[i];
    for (int i = 1; i <= a; i ++ ) {
        for (int j = 0; j <= b; j ++ ){
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i]){
                dp[i][j] = max(dp[i][j],dp[i][j - v[i]] + w[i]);
            }
        }
    }
    cout << dp[a][b] << endl;
}

//多重背包问题

#include <iostream>

using namespace std;

int a,b;
const int N = 101000;
int v[N],w[N];
int dp[N];

int main(){
    cin >> a >> b;
    int t = 0;
    for (int i = 1; i <= a; i ++ ) {
        int m,n,g;
        cin >> m >> n >> g;
        int k = 1;
        while (k < g) {
            t ++;
            v[t] = k * m;
            w[t] = k * n;
            g -= k;
            k *= 2;
        }
        if (g > 0) {
            t ++;
            v[t] = g * m;
            w[t] = g * n;
        }
    }
    for (int i = 1; i <= t; i ++ ) {
        for (int j = b; j >= v[i]; j -- ){
            dp[j] = max(dp[j],dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[b];
}

//分组背包

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>

#define ll long long
#define rep(i,a,n) for(int i = a; i <= n; i ++)
#define per(i,a,n) for(int i = n; i >= a; i --)
#define pb push_back

const ll N = 1e5;
ll dp[N];

void solve(){
    ll n,v;
    std::cin >> n >> v;
    rep(i,1,n){
        ll s;
        std::cin >> s;
        std::vector<ll>V(s + 1),W(s + 1);
        rep(j,1,s) std::cin >> V[j] >> W[j];
        per(j,0,v){
            rep(k,1,s){
                if(j >= V[k]) dp[j] = std::max(dp[j],dp[j - V[k]] + W[k]);
            }
        }
    }
    std::cout << dp[v] << "\n";
    return;
}

int main(){
//  int t;
//  std::cin >> t;
//  while(t --)
    solve();
    return 0;
}