senzori

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 $[T_{1,i},T_{2,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 $d_i$, iar datele trebuie să fie transmise într-un interval de timp $[t_{start,i},t_{start,i+d_i}) \subseteq [T_{1,i},T_{2,i})$ (momentul $t_{start,i}$ nu este dat).

Datele unui senzor $i$ au o valoare $v_i$ (î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 \leq i < N)$ trebuie să fie disjuncte: $[t_{start,i},t_{start,i+d_i}) \cap [t_{start,i+1},t_{start,i+1+d_{i+1}})$ = $\emptyset$

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 ($[T_{1,i},T_{2,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: $T_{1,i} \ T_{2,i} \ d_i \ v_i$; 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 și precizări

• $1 \leq N \leq 2 \ 000$
• $0 \leq T_{1,i} < T_{2,i} \leq 2 \ 000$
• $1 \leq d_i \leq T_{2,i}-T_{1,i}$
• $1 \leq v_i \leq 10 \ 000$

Exemplu

senzori.in

4
0 5 3 6
1 4 3 7
2 8 3 5
6 8 2 5

senzori.out

16

Explicație

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$.