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

int main() {
    int N, V;
    cin >> N >> V;
    vector<int> w(N + 1), v(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> v[i];
    }
    vector<int> dp(V + 1, 0);  // dp[j] 表示容量为 j 时的最大价值
    
    for (int i = 1; i <= N; i++) {
        for (int j = w[i]; j <= V; j++) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    cout << dp[V];
    return 0;
}