Fişierul intrare/ieşire:	heavymetal.in, heavymetal.out	Sursă	preONI 2008, Runda 4
Autor	Andrei Grigorean	Adăugată de	Andrei Grigorean •wefgef
Timp execuţie pe test	0.1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Heavy metal

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.

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.

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.

Restrictii

• 1 ≤ N ≤ 100000
• 1 ≤ A_i, B_i ≤ 10⁹
• A_i < B_i
• Pentru 40% din teste 1 ≤ N, A_i, B_i ≤ 1000

Exemplu

Explicatie

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

Cum se trimit solutii?