Se consideră n cuburi numerotate de la 1 la n pentru care se cunosc latura și culoarea. Să se genereze toate turnurile de înălțime H ce se pot forma cu cele n cuburi, astfel încât fiecare turn să respecte următoarele condiții:

• orice cub se așează peste un altul ce are latura mai mare sau egală cu a lui;
• să nu existe două cuburi consecutive de aceeași culoare;

Date de intrare

Fișierul de intrare turn.in conține pe prima linie două numere naturale n și H, iar pe următoarele n linii descrierea cuburilor. Linia i+1 conține descrierea cubului i sub forma: latură culoare.

Date de ieșire

Fișierul de ieșire turn.out va conține soluțiile generate în ordinea lexicografică a indicilor. O soluție este validă dacă conține descrierea indicilor cuburilor care alcătuiesc turnul de înălțime H.

Restricții și precizări

• 1 ≤ n < 15
• 1 ≤ H ≤ 50
• 1 ≤ latura ≤ 10
• 1 ≤ culoare ≤ 5
• nu există cuburi identice
• pentru datele de intrare există întotdeauna soluție

Exemplu

turn.in

5 5
1 1
2 1
1 2
2 2
3 1

turn.out

2 4 1 
4 2 3 
5 3 1 
5 4 

Explicație

Primul turn este format din cuburile: 2 (2,1), 4 (2,2), 1 (1,1).
Al doilea turn este format din cuburile: 4 (2,2), 2 (2,1), 3 (1,2)
etc.

#include <bits/stdc++.h>
using namespace std;

ifstream cin ("turn.in");
ofstream cout ("turn.out");

struct poz
{
    int i , j;
}a[20];
int n , h , x[101], p[101];

void afisare(int k)
{
    for(int i = 1; i <= k; i ++)
        cout << x[i] << ' ';
    cout << '\n';
}
void back(int k , int h , int start)
{
    if(h == 0)
    {
        afisare(k);
        return;
    }
    for(int i = 1 ; i <= n ; i ++)
    {
        if(a[start].j != a[i].j && a[start].i >= a[i].i && !p[i])
        {
            p[i] = 1;
            x[k + 1] = i;
            back(k + 1 , h - a[i].i , i);
            p[i] = 0;
        }
    }

}
int main()
{
    cin >> n >> h;
    for (int i = 1; i <= n; ++ i)
        cin >> a[i].i >> a[i].j;
    a[0].i = 2000000000;
    back(0 , h , 0);
    return 0;
}