#include <stdio.h>
long long max(long long a, long long b)
{
return a > b ? a : b;
}
int main(void)
{
FILE *input = fopen("rucsac.in", "r");
FILE *output = fopen("rucsac.out", "w");
size_t n, G;
fscanf(input, "%ld", &n);
fscanf(input, "%ld", &G);
long long int price[10000], weight[10000];
long long int optim[10000];
int sol = 0;
optim[0] = 0;
for(size_t i = 0;i < n;i++){
fscanf(input, "%lld", &weight[i]);
fscanf(input, "%lld", &price[i]);
}
for(size_t i = 0;i < n;i++){
for(int j = G - weight[i];j >= 0; --j){
optim[j + weight[i]] = max(optim[j + weight[i]], optim[j] + price[i]);
sol = max(sol, optim[j + weight[i]]);
}
}
printf("%d", sol);
fclose(input);
fclose(output);
return 0;
}