heavymetal

Heavy metal

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

Poveste si cerinta...

Miruna a intrat de curand in afacerea cu muzica buna. Ea s-a decis sa organizeze un festival de heavy metal si a cumparat o sala de concerte. La festival a invitat $N$ formatii, insa fiecare formatie poate sa cante un anumit interval fixat de timp. Deoarece fanii sunt scandalagii, Miruna doreste sa selectioneze formatiile ce vor canta astfel incat timpul total in care cineva concerteaza sa fie cat mai mare. In alegerea formatiilor trebuie sa aiba grija sa nu existe $2$ formatii care sa concerteze in acelasi timp.

h2. Date de intrare

Fisierul de intrare $heavymetal.in$ ...

Prima linie a fisierului de intrare $heavymetal.in$ contine un numar natural $N$, avand semnificatia din enunt. Urmeaza $N$ linii pe care se vor gasi cate doua valori $A{~i~}$ si $B{~i~}$, reprezentand intervalele de timp in care pot canta formatiile.

h2. Date de iesire

In fisierul de iesire $heavymetal.out$ ...

In fisierul de iesire $heavymetal.out$ se va gasi un singur numar reprezentand suma maxima a intervalelor de timp in care vor canta formatiile.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 100000$
* $1 ≤ A{~i~}, B{~i~} ≤ 10^9^$
* $A{~i~} < B{~i~}$
* Pentru $40%$ din teste $1 &le; N, A{~i~}, B{~i~} &le; 1000$

h2. Exemplu
table(example). |_. heavymetal.in |_. heavymetal.out |

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

| 4
  3 5
  5 10
  3 4
  1 2
| 8

|
h3. Explicatie

...

Vor canta formatiile $1$, $2$ si $4$, iar timpul total va fi $2 + 5 + 1 = 8$.

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

2713