De-a lungul autostrăzii Soarelui sunt amplasaţi N senzori, numerotaţi în ordinea de la Bucureşti spre Constanţa, de la 1 la N. În timpul unei zile, senzorii înregistrează date în continuu, cu excepţia unui anumit interval de timp; mai exact, pentru orice senzor i există un interval [T1,i,T2,i) în care senzorul trebuie să trimita datele înregistrate către staţia centrală (acest interval de timp poate fi diferit de la un senzor la altul). Durata de transmitere a datelor senzorului i este di, iar datele trebuie să fie transmise într-un interval de timp
(momentul tstart,i nu este dat).
Datele unui senzor i au o valoare vi (în funcţie de importanţa strategică a amplasării senzorului). Senzorii comunică wireless cu staţia centrală, pe aceeaşi frecvenţă, şi de aceea pot apărea interferenţe la transmisia datelor senzorilor cu numere de ordine consecutive. Aşadar, intervalele de timp în care sunt transmise datele a doi senzori i şi i+1 (1≤i<N) trebuie să fie disjuncte:
Această restricţie poate conduce la situaţia neplacută în care nu toţi senzorii vor putea trimite datele către staţia centrală în intervalul de timp disponibil ([T1,i,T2,i) pentru senzorul i). În acest caz, se doreşte determinarea unei submulţimi de senzori care vor transmite datele către staţia centrală şi pentru care suma valorilor datelor transmise este maximă.
Cerinţă
Să se determine suma maximă a valorilor datelor transmise de o submulţime a celor N senzori, astfel încât transmisia datelor acestor senzori să respecte toate restricţiile specificate.
Date de intrare
Fişierul de intrare senzori.in conţine pe prima linie numărul natural N, reprezentând numărul de senzori. Fiecare dintre următoarele N linii conţine câte 4 numere întregi separate prin spaţiu: T1,i T2,i di vi; a i-a dintre aceste linii corespunde senzorului cu numărul i.
Date de ieşire
În fişierul de ieşire senzori.out veţi afişa suma maximă a valorilor datelor transmise de o submulţime de senzori care poate trimite datele catre staţia centrală respectând toate restricţiile specificate în enunţ.
Restricţii
1 ≤ N ≤ 2000
0 ≤ T1,i < T2,i ≤ 2000
1 ≤ di ≤ T2,i-T1,i
1 ≤ vi ≤ 10000
Exemple
senzori.in
senzori.out
Explicaţii
4
0 5 3 6
1 4 3 7
2 8 3 5
6 8 2 5
16
Senzorii care vor trimite date către staţia centrală sunt: 1, 3 şi 4. Senzorul 1 va trimite datele în intervalul [0,3), senzorul 3 va trimite datele în intervalul [3,6), iar senzorul 4 în intervalul [6,8). Valoarea totală a datelor trimise este 6+5+5=16.
