// Student Rapeanu-Andreescu Stefan
// Faculty of Mathematics and Computer Science, University of Bucharest

#include <cstdio>
#include <cassert>

namespace InfoArena {
	namespace Arhiva_educationala {
		class PROBLEMA_Problema_rucsacului {
		private:
			static const unsigned int MAXN=5001;
			static const unsigned int MAXG=10001;
			int n, g, answer;
			int w[MAXN], p[MAXN], dp[MAXG];
		public:
			void Read() {
				FILE *ifp=fopen("rucsac.in", "r");
				assert(fscanf(ifp, "%d %d\n", &n, &g));
				for (int i=1;i<=n;++i)
					assert(fscanf(ifp, "%d %d\n", &w[i], &p[i]));
				fclose(ifp);
			}
			void Process() {
				dp[0]=0;
				answer=0;
				for (int i=1;i<=n;++i)
					for (int j=g-w[i];j>=0;--j)
						if (dp[j+w[i]]<dp[j]+p[i])
						{
							dp[j+w[i]]=dp[j]+p[i];
							if (dp[j+w[i]]>answer)
								answer=dp[j+w[i]];
						}
			}
			void Print() {
				FILE *ofp=fopen("rucsac.out", "w");
				fprintf(ofp, "%u", answer);
				fclose(ofp);
			}
			void Solve()
			{
				Read();
				Process();
				Print();
			}
		} Problema_rucsacului;
	}
}
int main()
{
	InfoArena::Arhiva_educationala::Problema_rucsacului.Solve();
	return 0;
}