Fişierul intrare/ieşire:	zmeu2.in, zmeu2.out	Sursă	OJI 2003, clasele 11-12
Autor	Dana Lica	Adăugată de	Cosmin-Mihai Tutunaru •stocarul
Timp execuţie pe test	0.1 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Zmeu2

Un zmeu cu N capete călătoreşte din poveste în poveste, iar în poveştile tradiţionale întâlneşte câte un Făt Frumos care-l mai scurtează de câteva capete, în timp ce în poveştile moderne salvează omenirea mâncând în timp record, cu toate capetele lui, insecte ucigaşe apărute prin mutaţii genetice. Într-o seară, el îşi planifică o succesiune de poveşti cărora să le dea viaţă. El ştie P poveşti numerotate de la 1 la P, durata fiecăreia şi numărul de capete pe care le pierde în fiecare poveste. Mai ştie o mulţime de K perechi de poveşti care nu pot fi spuse una după alta.

Cerinţă

Ştiind că trebuie să înceapă cu povestea 1 şi să încheie succesiunea cu povestea P, ajutaţi bietul zmeu să aleagă una sau mai multe poveşti intermediare astfel încât durata totală să fie minimă şi să rămână cu cel puţin un cap la sfârşitul tuturor poveştilor.

Date de intrare

Fişierul de intrare zmeu2.in conţine pe prima linie numerele N, P şi K despărţite prin câte un spaţiu. Pe următoarele P linii se află câte o pereche de numere d_i şi c_i (separate prin câte un spaţiu) ce reprezintă durata şi capetele tăiate pentru fiecare poveste. Iar pe ultimele K linii se află câte o pereche de numere p_i şi p_j (separate prin câte un spaţiu) ce semnifică faptul că povestea p_j nu poate fi spusă după povestea p_i.

Date de ieşire

În fişierul de ieşire zmeu2.out veţi afişa un singur număr natural reprezentând durata (minimă) a succesiunii de poveşti, sau valoarea -1 dacă nu există o astfel de succesiune.

Restricţii

• 2 ≤ N ≤ 500
• 1 ≤ P ≤ 200
• 0 ≤ K ≤ 30.000
• Valorile reprezentând duratele şi numărul de capete sunt numere naturale (duratele fiind strict pozitive), nedepăşind valoarea 10.

Exemplu

Cum se trimit solutii?