//#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
const int Max=10005;
int viz[Max][Max],n,g,w[Max],p[Max],profit[Max];
void citire()
{
    in>>n>>g;
    for(int i=1;i<=n;i++)
    {
        in>>w[i]; in>>p[i];
    }
}
void sol()
{
    int q;
    for(int G=1;G<=g;G++)
    {
        profit[G]=profit[G-1];
        for(int i=1;i<=n;i++)
          if(w[i]<=G && !viz[w[i]][p[i]])
        {
          if(profit[G-w[i]]+p[i]>profit[G])
          {
              profit[G]=profit[G-w[i]]+p[i];
              q=i;
          }
        }
        viz[w[q]][p[q]]=1;
        cout<<q<<" ";
    }

out<<profit[g];

}
int main()
{
   citire();
   sol();
    return 0;
}