#include <bits/stdc++.h>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int nmax = 5005;
const int wmax = 10005;
int dp[nmax][wmax];
struct object {
int weight;
int value;
};
int main() {
int N, maxWeight;
fin >> N >> maxWeight;
vector<object> objects(N + 1);
for(int i = 1; i <= N; ++i) {
fin >> objects[i].weight;
fin >> objects[i].value;
}
vector<int> maxProfit(maxWeight + 5, 0);
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= maxWeight; ++j) {
if(j >= objects[i].weight)
maxProfit[j] = max(maxProfit[j], maxProfit[j - objects[i].weight] + objects[i].value);
else
maxProfit[j] = maxProfit[j];
}
/*dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - objects[i].weight] + objects[i].value);
else dp[i][j] = dp[i - 1][j];*/
fout << maxProfit[maxWeight] << '\n';
return 0;
}