Cerința

Cercetătorii bistrițeni vor să creeze cea mai puternica soluţie stabilă, în limita elementelor disponibile. Ei deţin N elemente chimice reprezentate de numerele 1,2,3...N, cu puteri cunoscute. Puterea unei soluții este dată de suma puterilor elementelor. Nu pot să amestece orice elemente, pentru că soluţia ar deveni instabilă. Ei pot să combine elementele după anumite reguli:

1) Primul element al soluţiei poate fi oricare.
2) Dacă ultimul element al soluţiei curente este i, atunci următorul element trebuie să aparţină intervalului [si,di], pentru că altfel soluţia ar deveni instabilă.

Tu fiind noul angajat trebuie să găseşti puterea cea mai mare unei soluţii.

Date de intrare

Fișierul de intrare chimic.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale reprezentând puterile elementelor chimice. Pe următoarele N linii se va afla câte o pereche de 2 numere, reprezentând intervalul din care poate fi ales următorul element.

Date de ieșire

Fișierul de ieșire chimic.out va conține pe prima linie numărul P reprezentând puterea cea mai mare unei soluţii.

Restricții și precizări

• 1 ≤ N ≤ 100000;
• Dacă un element nu poate fi urmat într-o soluţie de niciun alt element, atunci intervalul corespunzător va fi -1 -1;
• Pentru fiecare interval [si,di] avem: i < si ≤ di, cu excepția cazului -1 -1 ;
• Intervalul corespunzător elementului N este -1 -1;
• Puterile elementelor sunt numere naturale mai mici sau egale ca 100000;
• Acest experiment se desfăşoară în viitorul îndepărtat, fiind descoperite deja 100000 elemente chimice.

Exemplu:

chimic.in

7
10 1 5 11 3 4 8 
2 4
5 6
6 7
-1 -1
6 7
7 7
-1 -1

chimic.out

27

Explicație

În fișierul de intrare sunt 7 elemente, cea mai bună combinaţie este reprezentată de elementele 1,3,6,7 având puterea 10+5+4+8=27.