//最优的完全背包
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int n, m;
int f[N]; //当前（第几件）的数据
int v[N], w[N]; //物品体积，价值

int main(){

    cin >> n >> m;

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

    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] = max (f[j], f[j - v[i]] + w[i]);

    cout << f[m];

    return 0;
}

//第一次修改
    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; j >= k * v[i]; k ++)
                f[i][j] = max (f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
//按照背包的思路，然后书写代码。不同于01背包，多了一层 k 循环，进行筛选该物品需要多少件。
/*f[i][j] = max (f[i][j], f[i - 1][j - v[i] * k] + w[i] * k)中 max() 里的f[i][j]，其实就是f[i][j] = f[i - 1][j]
这一步也算进去了，所以 max() 里是不选择第i件与选择几件第i件进行对比，可以与01背包进行比较
*/


//第二次修改
    for (int i = 1; i <= n; i ++ )
            for (int j = m; j >= 0; j -- )
                for (int k = 0; j >= k * v[i]; k ++)
                    f[j] = max (f[j], f[j - v[i] * k] + w[i] * k);
//修改时做了类似01背包的优化，将j的顺序进行逆置，并消去一元，但是因为三重循环所以还是过于冗杂


//第三次修改
    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] = max (f[j], f[j - v[i]] + w[i]);
//第三次修改的时候观察 f[j] 和 f[j - v[i]] 的关系，然后进行简化。
/*f[j] = max (f[j], f[j - v[i] *  k] + w[i] * k)
  f[j-v[i]] = max ( f[j - v[i]], f[j - v[i] * (k+1)] + w[i] * k) 差一个 w[i]，所以进行替换*/
//但是 j 循环这里算的数就是 f[i] 本身，不需要逆置，其实这是由第一次代码直接到的第三次代码