Fişierul intrare/ieşire:	senzori.in, senzori.out	Sursă	Lot 2008 - Piatra Neamt, Baraj2
Autor	Mugurel Ionut Andreica	Adăugată de	Airinei Adrian •astronomy
Timp execuţie pe test	0.05 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Senzori

De-a lungul autostrazii Soarelui sunt amplasati N senzori, numerotati in ordinea de la Bucuresti spre Constanta, de la 1 la N. In timpul unei zile, senzorii inregistreaza date in continuu, cu exceptia unui anumit interval de timp; mai exact, pentru orice senzor i exista un interval [T_1,i,T_2,i) in care senzorul trebuie sa trimita datele inregistrate catre statia centrala (acest interval de timp poate fi diferit de la un senzor la altul). Durata de transmitere a datelor senzorului i este d_i, iar datele trebuie sa fie transmise intr-un interval de timp [t_start,i,t_start,i+d_i) ⊆ [T_1,i,T_2,i) (momentul t_start,i nu este dat). Datele unui senzor i au o valoare v_i (in functie de importanta strategica a amplasarii senzorului). Senzorii comunica wireless cu statia centrala, pe aceeasi frecventa, si de aceea pot aparea interferente la transmisia datelor senzorilor cu numere de ordine consecutive. Asadar, intervalele de timp in care sunt transmise datele a doi senzori i si i+1 (1≤i<N) trebuie sa fie disjuncte: [t_start,i,t_start,i+d_i) ∩ [t_start,i+1,t_start,i+1+d_i+1) = ∅. Aceasta restrictie poate conduce la situatia neplacuta in care nu toti senzorii vor putea trimite datele catre statia centrala in intervalul de timp disponibil ( [T_1,i,T_2,i) pentru senzorul i). In acest caz, se doreste determinarea unei submultimi de senzori care vor transmite datele catre statia centrala si pentru care suma valorilor datelor transmise este maxima.
Sa se determine suma maxima a valorilor datelor transmise de o submultime a celor N senzori, astfel incat transmisia datelor acestor senzori sa respecte toate restrictiile specificate.

Date de intrare

Fisierul de intrare senzori.in contine pe prima linie numarul natural N, reprezentand numarul de senzori. Fiecare dintre urmatoarele N linii contine cate 4 numere intregi separate prin spatiu: T_1,i T_2,i d_i v_i; a i-a dintre aceste linii corespunde senzorului cu numarul i.

Date de iesire

In fisierul de iesire senzori.out veti afisa suma maxima a valorilor datelor transmise de o submultime de senzori care poate trimite datele catre statia centrala respectand toate restrictiile specificate in enunt.

Restrictii

• 1 ≤ N ≤ 2000
• 0 ≤ T_1,i < T_2,i ≤ 2000
• 1 ≤ d_i ≤ T_2,i-T_1,i
• 1 ≤ v_i ≤ 10000

Exemplu

Explicatie

Senzorii care vor trimite date catre statia centrala sunt: 1, 3 si 4. Senzorul 1 va trimite datele in intervalul [0,3), senzorul 3 va trimite datele in intervalul [3,6), iar senzorul 4 in intervalul [6,8). Valoarea totala a datelor trimise este 6+5+5=16.

Cum se trimit solutii?