#include <bits/stdc++.h>

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, g,dp[5005],greutate,profit;

int main()
{
fin>>n>>g;
// dp[i] profitul maxim pentru obiecte cu greutatea i
for (int i = 1; i <= n; i++){
    fin>>greutate>>profit;
    for (int j = g - greutate; j >= 0; j--){
        dp[j+greutate] = max(dp[j+greutate], dp[j] + profit);
    }
}
int Max = 0;
for (int i = 1; i <= g; i++){
    Max = max(Max, dp[i]);
}
fout << Max;

    return 0;
}