#include <fstream>
using namespace std;
int v[10001],r[10001];
int main()
{
    int n,gr,x,y,i,j,s=0;
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");
    f>>n>>gr;
    for (i=1;i<=n;i++)
    {
        f>>x>>y;
        for (j=gr-x;j>=0;j--)
            if (v[j]+y>v[j+x])
            {
                v[j+x]=v[j]+y;
                if (v[j+x]>s)
                    s=v[j+x];
            }
    }
    for (i=1;i<=gr;i++)
        g<<v[i]<<" ";
    g<<'\n';
    g<<s;
    return 0;
}