cover

Cover

== include(page="template/taskheader" task_id="cover") ==

Poveste si cerinta...

Se considera $N$ intervale inchise, avand extremitatile numere naturale cuprinse intre $1$ si $L$. Fiecare numar natural $i$ din intervalul $[1, L]$ are asociata o pondere $c{~i~}$.
Numim acoperire o multime de numere naturale cuprinse intre $1$ si $L$ cu proprietatea ca fiecare interval contine cel putin un element al multimii. Costul unei acoperiri este egal cu suma ponderilor numerelor din acoperire.
 
Pentru un set de intervale dat sa se determine costul minim al unei acoperiri.

h2. Date de intrare

...

Fisierul de intrare $cover.in$ contine pe prima linie cele doua numere naturale $N L$ separate printr-un spatiu. Pe urmatoarea linie se afla $L$ numere naturale separate prin cate un spatiu $c{~1~} c{~2~} ... c{~L~}$ reprezentand ponderile numerelor naturale din intervalul $[1, L]$. Urmatoarele $N$ linii contin fiecare cate doua numere naturale $a b (1 ≤ a ≤ b ≤ L)$ reprezentand extremitatile intervalelor.

h2. Date de iesire

...

Fisierul de iesire $cover.out$ va contine o singura linie pe care va fi scris un numar natural reprezentand costul minim al unei acoperiri.
 
h2. Restrictii si precizari

h2. Restrictii

* $1 ≤ N ≤ 60 000$
* $1 ≤ L ≤ 1 000 000$
* $0 ≤ c{~i~} ≤ 1024$, pentru orice $1 ≤ i ≤ L$
* Pentru @40%@ din teste $N ≤ 1 000$ si $L ≤ 10 000$

* $... ≤ ... ≤ ...$
h2. Exemplu

h2. Exemple

table(example). |_. cover.in |_. cover.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 2 5
100 5 9 6 90
1 3
3 5
| 9 |
| 4 10
1 3 6 4 5 1 0 1 3 2
1 3
3 5
6 9
4 4
| 5 |

h3. Explicatie

...

# Se construieste acoperirea {{$3$}} care are costul {$9$}. Elementul $3$ apartine ambelor intervale date in fisierul de intrare.
Exista si alte acoperiri posibile de exemplu {{$2, 4$}} dar costul acesteia este $11$ care nu este minim.
# Se construieste acoperirea {{$1, 4, 7$}} care are costul {$5$}.

== include(page="template/taskfooter" task_id="cover") ==

== SmfTopic(topic_id="...") ==

1847