#include <bits/stdc++.h>
using namespace std;ifstream fin("rucsac.in");ofstream fout("rucsac.out");int n,gmax;int c[5010],g[5010];int cmax[10010];void citire();void pd();int main(){citire(); pd();fout<<cmax[gmax]<<'\n';return 0;}void citire(){int i;fin>>n>>gmax;for(i=1;i<=n;i++)fin>>g[i]>>c[i];}void pd(){int i,x;for(i=1;i<=n;i++)for(x=gmax;x>=1;x--)if(x-g[i]>=0)cmax[x]=max(c[i]+cmax[x-g[i]],cmax[x]);}