cofetar

La un concurs de gastronomie, secţiunea “Cofetărie”, proba eliminatorie constǎ în pregătirea rapidă a celei mai ieftine prăjituri.
Cofetarii participanţi au la dispoziţie $N$ tipuri de ingrediente, numerotate distinct cu valori de la $1$ la $N$. Fiecare ingredient este disponibil în cantităţi nelimitate. Pentru fiecare ingredient este cunoscut preţul pentru $10$ grame.
Se ştie cǎ existǎ ingrediente care nu pot fi combinate în aceeaşi prǎjiturǎ (le vom numi ingrediente incompatibile). Prăjitura trebuie sǎ conţinǎ exact $M$ ingrediente compatibile, în proporţii fixe date $pr_1, pr_2, \dots pr_M$. Mai exact, primul ingredient ales reprezintǎ $pr_1\%$ din greutatea prǎjiturii, al doilea ingredient reprezintǎ $pr_2\%$ din greutatea prǎjiturii, etc.

Observaţie: Nimeni nu a pomenit nimic despre gustul prăjiturii…

Cerinţă

Scrieţi un program care să determine cele $M$ ingrediente compatibile, cu care, în proporţiile date $pr_1, pr_2, \dots, pr_M$, sǎ poată fi preparat $1$ Kg din cea mai ieftină prăjitură.

Date de intrare

Datele de intrare se citesc din fişierul text cofetar.in cu următoarea structură

• $N$ - numărul de ingrediente disponibile
• $p_1, p_2, \dots, p_N$ - preţurile pe $10$ gr ale fiecărui ingredient
• $k$ - numărul de relaţii de incompatibilitate
• $x_1 \ y_1$ - ingredientele $x_1$ şi $y_1$ sunt incompatibile
• $x_2 \ y_2$ - ingredientele $x_2$ şi $y_2$ sunt incompatibile
• $\dots$
• $x_k \ y_k$ - ingredientele $x_k$ şi $y_k$ sunt incompatibile
• $M$ - numărul de ingrediente ce trebuie folosite în prǎjiturǎ
• $pr_1, pr_2, \dots, pr_M$ - proporţiile în care apar cele $M$ ingrediente în prǎjiturǎ

Date de ieșire

Datele de ieşire se vor scrie in fişierul text cofetar.out cu următoarea structură:

• $C_{min}$ - costul unui Kg din cea mai ieftină prăjitură
• $c_1 \ c_2 \dots c_M$ - ingredientele alese

Restricții și precizări

• Toate valorile care intervin în enunţul problemei sunt numere naturale nenule.
• Datele de intrare sunt corecte şi pentru datele de test existǎ întotdeauna soluţie.
• $1<M<N<30$
• $0<p_i<1 \ 000$
• $pr_1 + pr_2 + \dots + pr_M = 100$
• $x_i, y_i$ din $\{1,2,\dots,N \}$, , $\forall i$ din $\{1,2,\dots,k \}$
• În cazul în care există mai multe soluţii pentru aceeaşi valoare minimă a prăjiturii se va afişa secvenţa de ingrediente cea mai mică din punct de vedere lexicografic (de exemplu secvenţa $5 \ 4 \ 6 \ 2$ este mai mică din punct de vedere lexicografic decât secvenţa $5 \ 4 \ 3 \ 1$)

Exemplu

cofetar.in

6
50 20 70 90 30 100
4
1 3 
1 5 
3 4
3 5
4
30 20 40 10

cofetar.out

4500
5 4 2 6