Zmeu2

zmeu2

== include(page="template/taskheader" task_id="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 seccesiune 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.
 
h2. 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.

Poveste şi cerinţă...

h2. 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ă poveste $p{~i~}$.

Fişierul de intrare $zmeu2.in$ ...

h2. 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.

În fişierul de ieşire $zmeu2.out$ ...

h2. Restricţii

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

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. zmeu2.in |_. zmeu2.out |

| 10 4 2
  2 6
  4 0
  1 3
  3 3
  3 2
  4 3
| 9

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="zmeu2") ==