#include <fstream>
#include <algorithm>

using namespace std;

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

int n,g,p[5005],w[5005],a[10005],b[10005];

int main()
{
    int i,j;

    fin>>n>>g;
    for(i=1; i<=n; i++) fin>>w[i]>>p[i];

    for(i=1; i<=n; i++)
       { for(j=1; j<=g; j++)
           if(w[i]>j) a[j]=b[j];
           else a[j]=max(b[j],b[j-w[i]]+p[i]);
         for(j=1;j<=g;j++)


    return 0;
}