#include <bits/stdc++.h>
using namespace std;
ifstream fin("meh.in");
ofstream fout("meh.out");
struct cub
{
int l, cul;
};
cub v[20];
int n, H, st[20],ap[20],sum[20];
void afisare(int k)
{
for(int i=1;i<=k;i++)
fout<<st[i]<<" ";
fout<<"\n";
}
int valid (int k)
{
if(k>1 && v[st[k]].l>v[st[k-1]].l)
return 0;
if(v[st[k]].cul==v[st[k-1]].cul)
return 0;
if(sum[k-1]+v[st[k]].l<=H){
sum[k] = sum[k-1] + v[st[k]].l;
return 1;
}
return 0;
}
// Uitee!! Partea asta de aici trebuie inlocuita cu un vector de aparitii!
//In loc sa umble prin stiva de fiecare data cand e apelat valid, e mai eficient sa verifici un vector. Ti-am modificat in functia back()!
// for (int i=1; i<k; i++)
// {
// if(st[i]==st[k])
// return 0;
// }
//aici trebuie sa verifici cu sume partiale! la fiecare pas faci un sum[k] = sum[k-1] + st[k] DACA sum[k-1] + st[k] e <=H
// altfel, calculeaza de fiecare data cand intra in valid_sol() suma din stiva, ceea ce ia destul timp
// Am pus sumele partiale in valid() pentru ca e mai ok si de citit si de controlat (sunt prea obosit sa-mi dau seama daca si mai eficient,
// dar presupun ca da :))
int valid_sol(int k)
{
if(sum[k]==H) return 1;
return 0;
}
void back (int k)
{
for(int i=1; i<=n; i++)
{ // incercam doar daca indicele (i) nu a aparut inainte in stiva
if(ap[i]==0){
ap[i]=1; // notam ca a aparut in stiva
st[k]=i;
if(valid(k))
if(valid_sol(k))
afisare(k);
else
back(k+1);
ap[i]=0; // cand se intoarce backu, indicele i dispare din stiva pentru ca nu mai e folosit, aparitia sa devine nula
}
}
}
int main()
{
fin>>n>>H;
for(int i=1;i<=n;i++)
fin>>v[i].l>>v[i].cul;
back(1);
return 0;
}
