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 pr1, pr2,…prM. Mai exact, primul ingredient ales reprezintǎ pr1% din greutatea prǎjiturii, al doilea ingredient reprezintǎ pr2% 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 pr1, pr2,…, prM, 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
p1 p2 … pN // preţurile pe 10 gr ale fiecărui ingredient
k // numărul de relaţii de incompatibilitate
x1 y1 // ingredientele x1 şi y1 sunt incompatibile
x2 y2 // ingredientele x2 şi y2 sunt incompatibile
...
xk yk // ingredientele xk şi yk sunt incompatibile
M // numărul de ingrediente ce trebuie folosite în prǎjiturǎ
pr1 pr2 … prM // proporţiile în care apar cele M ingrediente în prǎjiturǎ

Date de ieşire

Datele de ieşire se vor scrie in fişierele text cofetar.out cu următoarea structură:
Cmin // costul unui Kg din cea mai ieftină prăjitură
c1 c2 …cM // ingredientele alese

Restricţii

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<pi<1000
pr1+pr2+…+prM=100
xi, yi din {1,2,...,N}, xi<>yi, i din {1,2,...,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)

Exemple

cofetar.in	cofetar.out
6 50 20 70 90 30 100 4 1 3 1 5 3 4 3 5 4 30 20 40 10	4500 5 4 2 6

propunător: Prof. Marinel Şerban

Liceul de Informatica

marinel.serban@gmail.com