zmeu

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, semnificând faptul că a doua poveste din pereche nu poate fi spusă după prima poveste din pereche.

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 zmeu.in conţine pe prima linie numerele $n, p$ şi $k$ despărţite prin câte un spaţiu. Pe fiecare din 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 numărul de capete 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

Fişierul de ieşire zmeu.out conţine o singură linie pe care se află un număr natural reprezentând durata (minimă) a succesiunii de poveşti sau valoarea $–1$ dacă nu există o astfel de succesiune.

Restricţii şi precizări

• $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$.

Exemplu

zmeu.in

10 4 2
2 6
4 0
1 3
3 3
3 2
4 3

zmeu.out

9