Raspored

Ivica radi kao programer u jednom manjoj firmi gdje nerijetko dobiva velike količine zadataka od svog šefa. Ovoga puta Ivica je od šefa dobio popis zadataka koje mora odraditi. Za svaki zadatak Ivica zna u kojem vremenskom intervalu mu odgovara da krene raditi na tom zadatku te zna koliko vremena mu treba da odradi taj zadatak. Jednom kada započne neki zadatak prvo će ga dovršiti do kraja bez prekidanja i tek će onda prijeći na sljedeći zadatak. Također, Ivici je šef naglasio da je jako važno da se zadaci obavljaju točno redom kojim su navedeni jer se nadovezuju jedni na druge. Ivicu najviše dosađuje prazan hod između dva zadatka stoga bi htio što manje čekati između obavljanja neka dva zadatka. Pomozite mu i odredite koliko bi mu bila najdulja pauza između dva zadatka ako počne obavljati zadatke u optimalno vrijeme koje minimizira duljinu te najdulje pauze.

Ulazni podatci

Prvi redak sadrži prirodni broj N , broj zadataka. U sljedećih N redaka nalazi se prirodni brojevi Li , Ri , Di koji predstavljaju redom početak i kraj intervala u minutama u kojem Ivica može krenuti obavljati zadatak te koliko je vremena Ivici potrebno da riješi taj zadatak.

Izlazni podatci

U prvi i jedini redak ispišite duljinu tražene najdulje pauze u slučaju kada se zadaci rješavaju tako da je duljina te najdulje pauze minimizirana. Ako je nemoguće odraditi zadatke uz zadane intervale, ispišite -1.

Bodovanje

Podzadatak Bodovi Ograničenja

1 7 1 ≤ N ≤ 10, 1 ≤ Li ≤ Ri ≤ 20, Di = 1 2 14 1 ≤ N ≤ 100, 1 ≤ Li ≤ Ri ≤ 1000, 1 ≤ Di ≤ 10 3 19 1 ≤ N ≤ 1 000 000, 1 ≤ Li ≤ Ri ≤ 108 , 1 ≤ Di ≤ 108

Probni primjeri

ulaz ulaz ulaz

5 2 3 2 3 1 3 5 1 1 3 1 4 5 3 1 2 1 6 8 1 4 10 1 9 12 1 5 9 1 izlaz 12 13 4 izlaz -1 izlaz 2

2