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ța

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] ... 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 ≤ 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 și precizări

• 1 ≤ N ≤ 60 000
• 1 ≤ L ≤ 1 000 000
• 0 ≤ c[i] ≤ 1024, pentru orice 1 ≤ i ≤ L
• Pentru 40% din teste N ≤ 1000 şi L ≤ 10000.

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.