#include <fstream>
#include <algorithm>
using namespace std;
int D[100][100],G[100],P[100],n,C
;
ifstream f("rucsac.in");
ofstream g("rucsac.out");

int main()
{
    f>>n>>C;
    for(int i=1; i<=n; i++)
        f>>G[i]>>P[i];
    for(int i=1; i<=C; i++)
        for(int j=1;j<n;j++)
            if(G[j]==i)
            for(int t=j+1;t<=n;t++)
            if(G[j]==i&&G[t]==i)
             D[1][i]=max(P[j],max(D[1][i],P[t]));
             else
             D[1][i]=P[j];


        for(int i=1;i<=C;i++)
        if(G[n]==i&&P[n]>D[1][i])
        D[1][i]=P[n];






   for(int i=1; i<=C; i++)
        g<<D[1][i]<<' ';

for(int i=2; i<=n; i++)
        for(int j=1; j<=C; j++)
            D[i][j]=max(D[i-1][j],D[i-1][j-G[i]]+P[i]);

    g<<D[n][C];


    return 0;
}