Cu ocazia Festivalului Băuturilor Răcoritoare de anul acesta, Miruna vrea să organizeze un maraton de muzică care să înnebunească fanii şi care să o ajute să trăiască bine la bătrâneţe. Miruna dispune de o singură scenă, pe care vor concerta o parte dintre cele N formaţii care şi-au arătat interesul. Se cunoaşte pentru fiecare formaţie durata minimă de timp pentru care trupa este de acord să cânte, ora maximă la care trebuie să îşi încheie recitalul pentru a nu pierde avionul, precum şi profitul pe care l-ar aduce.

Cerinţă

Ajutaţi-o pe Miruna sa stabilească un program al formaţiilor ce vor cânta care să-i maximizeze profitul.

Date de intrare

Fişierul de intrare fbr.in conţine pe prima linie un număr natural N reprezentând numărul de formaţii. Pe fiecare dintre următoarele N linii, se vor afla câte trei numere naturale A B C, reprezentând durata minimă a unui concert, ora maximă de încheiere a concertului, respectiv profitul adus de fiecare dintre cele N formaţii.

Date de ieşire

Fişierul de ieşire fbr.out va conţine o singură linie pe care va fi scris un singur număr natural, reprezentând profitul maxim ce poate fi obţinut.

Restricţii şi precizări

• 1 <= N <= 1000
• 1 <= A_i, B_i <= 10000
• 1 <= C_i <= 100000
• Concertul începe la momentul de timp 0

Exemple

fbr.in	fbr.out	Explicaţii
4 4 7 20 3 7 10 1 4 15 4 11 25	60	Vor concerta formaţiile 3, 1 şi 4

Andrei Grigorean

Facultatea de Matematică şi Informatică, Universitatea din Bucureşti

andrei.grigorean@gmail.com