Fişierul intrare/ieşire:	concert.in, concert.out	Sursă	info-arena 1.0
Autor	Andrei Gonczi	Adăugată de
Timp execuţie pe test	0.2 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Concert

Un grup de N artisti a primit invitatii sa cante la un concert. Fiecarui artist i s-a trimis o invitatie pe care acesta era invitat sa cante intre orele A si B. Insa organizatorii acestui eveniment au gresit invitatiile si timpurile in care trebuiau sa cante anumiti artisti se suprapuneau. Artistii, fiind renumiti, nu accepta sa cante decat singuri. De asemenea ei cer despagubiri daca li se cere sa inceapa sa cante dupa ora A+1 sau sa termine inainte de ora B. Un anumit artist poate sa cante doar intre orele A si B de pe invitatie. Unele invitatii pot fi anulate, asa ca unii artisti pot sa nu cante deloc.

Cerinta

Cunoscandu-se intervalele intre care poate sa cante fiecare artist, profitul pe care il aduce fiecare artist pe unitatea de timp si despagubirile cerut in ambele cazuri mentionate mai sus, voi trebuie sa aflati care este suma maxima care poate fi obtinuta in concertul respectiv, si cum poate fi ea obtinuta.

Date de Intrare

Pe prima linie a fisierul concert.in se va afla N. Pe urmatoarele N linii ale fisierulul se vor gasi cate 5 numere separate prin cate un spatiu. Ele reprezinta A, B, profitul pe unitatea de timp si despagubirile in cazul in care artistul nu incepe sa cante in A+1 si respectiv daca nu termina de cantat in B.

Date de Iesire

Pe prima linie a fisierul concert.out se va afla suma maxima care poate fi obtinuta din concert.

Restrictii

• 1 ≤ N ≤ 1.000
• 1 ≤ A_i < B_i ≤ 2.000.000.000
• profitul adus de fiecare artist sau despagubirile cerute de fiecare dintre ei nu vor trece de valoare 500. Despagubirile se platesc o data, nu pe unitate de timp.
• daca artistul i are in contract intervalul (A_i,B_i) el poate canta intre momentele A_i+1 si B_i inclusiv.
• oricare doi artisti au intervalele diferite
• solutia nu va trece de valoare 2³¹-1
• Nu exista 2 artisti x si y astfel incat intervalul in care poate canta x sa fie complet inclus in intervalul lui y

Exemple

Explicatie

Artistul 1 canta intre orele 1 si 5, aducand un profit de (5-1+1)*10 = 50 si nu cere despagubiri, pentru ca a cantat intre orele stabilite in invitatie. Artistul 2 nu canta de loc. Artistul 3 canta intre orele 6 si 10, aducand un profit de (10-6+1)*12 = 60, insa i se platesc despagubiri in valoare de 4, pentru ca nu a inceput la ora la care i s-a spus in invitatie ca va incepe, ora A+1 = 4. Astfel artistul 3 aduce un profit de 60-4 = 56. Artistul 4 canta intre orele 11 si 12. Aducand un profit de 2*7 = 14, insa cere ambele despagubiri deci aduca un profit de 14-7-4 = 3. Artistul cu numarul 5 aduce un profitde 8*10 = 80, si nu cere despagubiri, pentru ca a cantat intre orele stabilite. Astfel, totalul se ridica la: 50+56+3+80=189.

Cum se trimit solutii?