Blistavost

Στην καρδιά της Κοιλάδας του Γυαλιού βρίσκεται ένας μυστηριώδης ακτινωτός ναός, ένα μέρος γνωστός για τη συλλογή του από μαγικούς κρυστάλλους που λάμπουν σαν τα αστέρια. Κάθε κρύσταλλος έχει μια ξεχωριστή δύναμη και εκπέμπει μια λάμψη που φωτίζει όλη την κοιλάδα, όσο παραμένει ανέγγιχτος.

Η νυχτερινή αποστολή του φύλακα του ναού είναι να αγγίξει ΜΟΝΟ τους κρυστάλλους που βρίσκονται εντός περιοχών καθορισμένων από τους κατοίκους της κοιλάδας, ενώ ταυτόχρονα πρέπει να τηρήσει όλες τις απαιτήσεις τους. Το αίτημα κάθε κατοίκου λέει στον φύλακα ποια περιοχή κρυστάλλων ΔΕΝ πρέπει να σταματήσει να λάμπει ΠΡΙΝ από την ώρα του ύπνου τους, καθώς φοβούνται το σκοτάδι.

Ο φύλακας ξεκινά το ταξίδι του από την είσοδο του ναού και πρέπει να συντονίσει προσεκτικά τις κινήσεις του ώστε οι κρύσταλλοι να σταματήσουν να λάμπουν την κατάλληλη στιγμή. Οι κρύσταλλοι είναι τοποθετημένοι σε μια ευθεία, σε απόσταση ενός μέτρου ο ένας από τον άλλο (ο πρώτος κρύσταλλος βρίσκεται σε απόσταση ενός μέτρου από την είσοδο). Ο φύλακας μπορεί να κινείται με ταχύτητα ενός μέτρου ανά δευτερόλεπτο και μπορεί να σταματά όποτε χρειάζεται. Ο χρόνος που απαιτείται για να αγγίξει ο φύλακας έναν κρύσταλλο και να κρύψει τη λάμψη του είναι αμελητέος. Δεδομένων των αιτημάτων των κατοίκων, ο φύλακας του ναού θέλει να γνωρίζει τον ελάχιστο αριθμό δευτερολέπτων που απαιτούνται για να ικανοποιήσει όλα τα αιτήματα (ο φύλακας δεν χρειάζεται να επιστρέψει στην αρχική του θέση).

Είσοδος

Στην πρώτη γραμμή θα δίνεται ένας ακέραιος ~N\le(1 \le N \le 5000)~, ο αριθμός των αιτημάτων των κατοίκων.

Στις επόμενες ~N~ γραμμές θα δίνονται ακέραιοι ~l_i~, ~r_i~, ~t_i\;(1 \le l_i\le r_i \le 1e18,\; 1 \le t_i \le 1e18)~, που αντιπροσωπεύουν τα αριστερά και δεξιά όρια της περιοχής κρυστάλλων και την ώρα ύπνου του κατοίκου, αντίστοιχα.

Έξοδος

Στην πρώτη και μοναδική γραμμή εκτυπώστε τον ελάχιστο χρόνο σε δευτερόλεπτα που απαιτείται ώστε ο φύλακας να ικανοποιήσει όλα τα αιτήματα.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~20~	~n \le 18~, ~l_i = r_i~ για κάθε ~i = 1, 2, . . . , n~
~2~	~25~	~l_i = 1~ για κάθε ~i = 1, 2, . . . , n~
~3~	~55~	~l_i = r_i~ για κάθε ~i = 1, 2, . . . , n~
~4~	~20~	Κανένας επιπλέον περιορισμός

Παραδείγματα

1ο

input

3
1 1 1
3 3 5
5 5 3

output

7

2ο

input

3
1 2 1
1 1 5
1 3 4

output

6

Επεξήγηση του δεύτερου παραδείγματος:

Ο φύλακας του ναού θα χρειαστεί πρώτα ~3~ δευτερόλεπτα για να φτάσει στον ~3~ο κρύσταλλο. Στη συνέχεια, θα περιμένει για ~1~ δευτερόλεπτο και θα σβήσει τη λάμψη του ~3~ου κρυστάλλου. Μετά από αυτό, θα χρειαστεί ~1~ δευτερόλεπτο για να πάει στον ~2~ο κρύσταλλο και να σβήσει τη λάμψη του. Τέλος, θα χρειαστεί ~1~ δευτερόλεπτο για να φτάσει στον ~1~ο κρύσταλλο και να μειώσει τη λάμψη του. Συνολικά, το ταξίδι του θα διαρκέσει ~6~ δευτερόλεπτα, που είναι ο ελάχιστος χρόνος που απαιτείται για να ικανοποιηθούν όλα τα αιτήματα.

3ο

input

3
6 6 6
8 8 7
9 9 9

output

9