//朴素写法
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int v[N], w[N];
int f[N][N];

int main()
{
    int n, C;
    cin >> n >> C;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= C; j++)
            for(int k = 0; k * v[i] <= j; k++)      // k * v[i] <= V 的时候要if + else
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);      //k = 0 的时候，f[i][j] = f[i - 1][j]

    cout << f[n][C] << endl;

    return 0;
}

//优化写法

//f[i][j] = max(f[i - 1][j], 、、、, f[i - 1][j - k * v[i]] + k * w[i])
//f[i][j - v[i]] = max(f[i - 1][j - v[i]], 、、、, f[i - 1][j - k * v[i]] + (k - 1) * w[i])

//f[i][j] = max(f[i - 1][j], f[i][j - v[i])

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int v[N], w[N];
int f[N][N];

int main()
{
    int n, C;
    cin >> n >> C;
    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= C; j++)
        {
            if(v[i] > j) f[i][j] = f[i - 1][j];
            else f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
        }

    cout << f[n][C] << endl;

    return 0;
}