#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.outt");

int n,G;
pair < int, int > adatok[10001];
int optimal[10001]={};
int teszt[10001]={};

void beolvas()
{
    f>>n>>G;
    int a,b;
    int i=1;
    while(f>>a>>b)
    {
        adatok[i].first=a;
        adatok[i].second=b;
        i++;
    }
}

void rucsac()
{
    optimal[adatok[1].first]=adatok[1].second;
    copy(optimal,optimal+G+1,teszt);
    for(int i=2;i<=G;i++)
    {
        for(int j=0;j<=G;j++)
        {
            if(optimal[j+adatok[i].first]<optimal[j]+adatok[i].second&&j+adatok[i].first<=G)
                teszt[j+adatok[i].first]=optimal[j]+adatok[i].second;
        }
        copy(teszt,teszt+G+1,optimal);
    }
    int maxi=0;
    cout<<endl;
    for(int i=1;i<=G;i++)
    {
        cout<<optimal[i]<<" ";
        if(optimal[i]>maxi)
            maxi=optimal[i];
    }
    cout<<endl<<maxi;
    g<<maxi;
}

int main()
{
    beolvas();
    for(int i=1;i<=n;i++)
    {
        cout<<adatok[i].first<<" "<<adatok[i].second<<endl;
    }
    rucsac();
    return 0;
}