Se consideră N intervale închise, având extremităţile numere naturale cuprinse între 1 şi L.
Fiecare număr natural i din intervalul [1, L] are asociată o pondere ci.
Numim acoperire o mulţime de numere naturale cuprinse între 1 şi L cu proprietatea că fiecare interval conţine cel puţin un element al mulţimii.
Costul unei acoperiri este egal cu suma ponderilor numerelor din acoperire.
Cerinţă
Pentru un set de intervale dat să se determine costul minim al unei acoperiri.
Date de intrare
Fişierul de intrare cover.in conţine pe prima linie cele două numere naturale N L separate printr-un spaţiu. Pe următoarea linie se află L numere naturale separate prin câte un spaţiu c1 c2 ... cL reprezentând ponderile numerelor naturale din intervalul [1, L]. Următoarele N linii conţin fiecare câte două numere naturale a b (1 ≤ a ≤ b ≤ L) reprezentând extremităţile intervalelor.
Date de ieşire
Fişierul de ieşire cover.out va conţine o singură linie pe care va fi scris un număr natural reprezentând costul minim al unei acoperiri.
Restricţii
1 ≤ N ≤ 60 000
1 ≤ L ≤ 1 000 000
0 ≤ ci ≤ 1024, pentru orice 1 ≤ i ≤ L
Pentru 40% din teste N ≤ 1000 şi L ≤ 10000.
Exemple
cover.in
cover.out
Explicaţii
2 5
100 5 9 6 90
1 3
3 5
9
Se construieşte acoperirea {3} care are costul 9. Elementul 3 aparţine ambelor intervale date în fişierul de intrare.
Există şi alte acoperiri posibile de exemplu {2, 4} dar costul acesteia este 11 care nu este minim.
4 10
1 3 6 4 5 1 0 1 3 2
1 3
3 5
6 9
4 4
5
Se construieşte acoperirea {1, 4, 7} care are costul 5.