Se consideră n mărgele numerotate de la 1 la n de culori și grad de strălucire diferite. Se generează toate posibilitățile de construire a unui colier de m mărgele distincte, astfel încât mărgelele aflate pe poziții învecinate să fie de culori diferite. Un colier este cu atât mai prețios (valoros) cu cât suma gradelor de strălucire a mărgelelor este mai mare.

Cerință

Să se determine cel mai prețios minim lexicografic colier format.

Date de intrare

Fișierul de intrare colier.in conține pe prima linie două numere naturale n și m, iar pe următoarele n linii descrierea mărgelelor. Linia i+1 conține descrierea mărgelei i sub forma: culoare grad_stralucire.

Date de ieșire

Fișierul de ieșire colier.out va conține pe prima linie, separate prin spațiu, cele m numere de ordine ale mărgelelor care formează colierul cel mai prețios.

Restricții și precizări

• 1 ≤ n ≤ 12
• 2 ≤ m < 10
• gradul de strălucire al mărgelelor este cuprins în intervalul [1..100]
• culoarea mărgelelor este dată sub forma unui număr natural nenul <20
• nu există mărgele identice
• colierul este circular – prima mărgea se învecinează cu ultima

Exemplu

colier.in

7 4
1 2 
3 2
2 1
2 3
1 3
2 2
3 1

colier.out

1 2 5 4

Explicație

Colierul format din mărgelele: 1,2,5,4 este colierul cel mai prețios minim lexicografic.
Gradul total de strălucire = 10.
Cu același grad maxim de strălucire sunt de exemplu și colierele: 1 4 5 2, 6 1 4 5.

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

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

struct poz
{
    int val , culoare , grad;
}a[15];
int x[15] , s[15] , maxi , n , m , rez[15] , p[15];

void back(int k , int sp)
{
    for(int i = 1 ; i <= n ; i++)
    if(!p[i])
    {
        x[k] = i;
        p[i] = 1;
        sp += a[x[k]].grad;
        if(k == 1 || a[x[k]].culoare != a[x[k - 1]].culoare)
        if(k <= m)
        {
            if(k == m)
            {
                if(sp > maxi && a[x[1]].culoare != a[x[m]].culoare)
                {
                    maxi = sp;
                    for(int j = 1 ; j <= m ; j++)
                        rez[j] = a[x[j]].val;
                }
            }
            else back(k + 1 , sp);
        }
        sp -= a[x[k]].grad;
        p[i] = 0;
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
    {
        a[i].val = i;
        cin >> a[i].culoare >> a[i].grad;
    }
    back(1 , 0);
    for(int i = 1 ; i <= m ; i++)
        cout << rez[i] << " ";
}