#include <iostream>
#include <fstream>

using namespace std;

class przedmiot{
    private:
    int waga;
    int cena;
    public:
    int getWaga(){
        return waga;
    }
    int getCena(){
        return cena;
    }
    int setWaga(int wg){
        waga=wg;
    }
    int setCena(int cn){
        cena=cn;
    }

};
void wypisz_wynik(int** s, int n, int W, przedmiot p[]){

    if(n==0 || W==0){
            cout<<endl;
        return;
    }
    if(s[n][W]==s[n-1][W] && s[n][W]!=(s[n-1][W-p[n-1].getWaga()])+p[n-1].getCena()){
        wypisz_wynik(s,n-1,W,p);
    }

    if(s[n][W]==s[n-1][W] && s[n][W]==(s[n-1][W-p[n-1].getWaga()])+p[n-1].getCena()){
        cout<<n<<" ";
        wypisz_wynik(s,n-1,W-p[n-1].getWaga(),p);
    }
    if(s[n][W]==s[n-1][W] && s[n][W]==(s[n-1][W-p[n-1].getWaga()])+p[n-1].getCena()){
        wypisz_wynik(s,n-1,W,p);
    }

    if(s[n][W]!=s[n-1][W] && s[n][W]==(s[n-1][W-p[n-1].getWaga()])+p[n-1].getCena()){
        cout<<n<<" ";
        wypisz_wynik(s,n-1,W-p[n-1].getWaga(),p);
    }

}



int main()
{
    fstream wej;
    fstream wyj;
    wej.open("In0302.txt",ios::in);
    wyj.open("Out0302.txt",ios::out);
    int n;
    int pom;
    int W; //rozmiar pleceaka
    wej>>n;
    wej>>W;
    przedmiot Przedmioty[n];
    for(int i=0;i<n;i++){
        wej>>pom;
        Przedmioty[i].setCena(pom);
        wej>>pom;
        Przedmioty[i].setWaga(pom);
    }

// algorytm zagadnienia plecakowego

 n++;
    W++;
    int **s= new int *[W];
    for(int i=0;i<n;i++){
        s[i]= new int[W];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<W;j++){
            if(i==0 || j==0){
                s[i][j]=0;
                continue;
            }
            if(Przedmioty[i-1].getWaga()>j){
                s[i][j]=s[i-1][j];
                continue;
            }
            s[i][j]=max(s[i-1][j-Przedmioty[i-1].getWaga()]+Przedmioty[i-1].getCena(),s[i-1][j]);
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<W;j++){
            cout<<s[i][j]<<" ";
        }
        cout<<endl;
    }
   wypisz_wynik(s,n-1,W-1,Przedmioty);

    return 0;
}