cover

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

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 $c_1 \ c_2 \dots c_L$ reprezentând ponderile numerelor naturale din intervalul $[1, L]$. Următoarele $N$ linii conţin fiecare câte două numere naturale $a$, $b \ (1 \leq a \leq b \leq 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 și precizări

• $1 \leq N \leq 60 \ 000$
• $1 \leq L \leq 1 \ 000 \ 000$
• $0 \leq c_i \leq 1 \ 024$, pentru orice $1 \leq i \leq L$
• Pentru $40\%$ din teste, $N \leq 1 \ 000$ şi $L \leq 10 \ 000$.

Exemplul 1

cover.in

2 5
100 5 9 6 90
1 3
3 5

cover.out

9

Explicație

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.

Exemplul 2

cover.in

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

cover.out

5

Explicație

Se construieşte acoperirea $\{1, 4, 7\}$ care are costul 5.