Županijska razina / Primjena algoritama OŠ 2020. / Osnovna škola (8. razred) - 3. zadatak

Mirko je postao DJ i večeras će puštati glazbu na tulumu posvećenom mladim informatičarima.

Na svoje je računalo s interneta (legalno) preuzeo N pjesama te ih treba složiti u playlistu.

Slagat će ih proizvoljnim redom, a svaku će pjesmu u playlistu staviti točno jednom.

Pjesme iz playliste puštati će na tulumu redom, jednu iza druge, bez pauza između.

Kako tulum ne može dugo trajati jer mladi informatičari moraju na spavanje, od svake pjesme iz liste pustit će samo dio.

Prvu pjesmu u playlisti pustit će od početka, tj. od njezine prve sekunde, do njezine Ki-te sekunde.

Svaku sljedeću pjesmu pustit će od njezine Pi-te do Ki-te sekunde. Zadnju iz liste pustit će od njezine Pi-te sekunde do kraja, tj. do njezine Ti-te sekunde.

Znamo da tulum službeno počinje s početkom prve, a završava s krajem zadnje pjesme iz playliste.

Mirko želi složiti pjesme u playlistu tako da tulum traje što dulje.

Napiši program koji će na osnovi zadanih podataka ispisati duljinu trajanja tuluma prema Mirkovoj želji.

Ulazni podaci

U prvom je retku prirodan broj N (2 ≤ N ≤ 100 000), broj pjesama iz teksta zadatka.

U i-tom od sljedećih N redaka su po tri prirodna broja Pi, Ki i Ti (2 ≤ Pi ≤ Ki < Ti ≤ 1000), brojevi iz teksta zadatka kojima se opisuje i-ta pjesma.

Izlazni podaci

U jedini redak ispiši prirodan broj, najveću duljinu trajanja tuluma koju Mirko može postići.

Primjer zadatka

Ulaz

3
2 4 5
2 2 3
3 3 7

Izlaz

10

Objašnjenje

Opis prvog probnog primjera: Mirko u playlistu može staviti pjesme onim redom kojim su zadane u probnom primjeru.

Tada će se prva pjesma izvoditi od prve do četvrte sekunde (ukupno četiri sekunde), druga pjesma samo njenu drugu sekundu (ukupno jedna sekunda), a zadnja od njene treće do sedme sekunde (ukupno pet sekundi).

Ukupno su se pjesme izvodile 4+1+5=10 sekundi što je ujedno i najdulje

izvođenje koje Mirko može postići.

Ulaz

4
4 6 7
3 4 5
4 4 8
2 2 5

Izlaz

14

Ulaz

2
2 6 8
3 3 4

Izlaz

10