Heavy metal

heavymetal

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

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.

Poveste si cerinta...

h2. Date de intrare

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.

Fisierul de intrare $heavymetal.in$ ...

h2. Date de iesire

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

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

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 |

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

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

|
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