#include <bits/stdc++.h>
using namespace std;ifstream in("rucsac.in");ofstream out("rucsac.out");int profit1[10001],profit2[10001],greut[5001],pro[5001];int main(){int n,g,maxim = 0,i,j;in>>n >>g;for(i=1;i<=n;i++)in >>greut[i]>>pro[i];for(i=1;i<=n;i++){for(j=greut[i];j<=g;j++){profit1[j]=max(profit2[j],profit2[j-greut[i]]+pro[i]);maxim=max(maxim,profit1[j]);}for(j=1;j<=g;j++)profit2[j]=profit1[j];}out<<maxim;}