#include <bits/stdc++.h>

using namespace std;
//完全背包的原始未优化版本
const int N = 1010;
int f[N][N];
int v[N], w[N];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d %d", &v[i], &w[i]);

    //多层循环，万恶之源
    //优化的策略是想办法干掉最里层的循环，就是经典的类比法对比公式，
    //f[i][j-v] 去类比，用一个式子代替掉一层循环，使得时间复杂度降低
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k * v[i] <= j; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);

    printf("%d\n", f[n][m]);
    return 0;
}