Setnja

Ο Mirko παίρνει όλους τους φίλους του σε μια συναυλία των Zaz που θα πραγματοποιηθεί σύντομα στο Ζάγκρεμπ. Έχει ήδη αποκτήσει τα εισιτήρια, και τώρα περπατά στη γειτονιά παραδίδοντάς τα σε όλους.
Η γειτονιά του Mirko μπορεί να αναπαρασταθεί με ένα καρτεσιανό επίπεδο. Ενώ περπατά, ο Mirko πατάει μόνο σε σημεία κιγκλίδας (ακέραιες συντεταγμένες) αυτού του επιπέδου. Κάνει ένα μόνο βήμα για να μετακινηθεί σε οποιοδήποτε από αυτά τα οκτώ γειτονικά σημεία πλέγματος (πάνω, κάτω, αριστερά, δεξιά ή διαγώνια προς οποιαδήποτε κατεύθυνση).
Κάθε ένας από τους φίλους του Mirko ζει επίσης σε κάποιο σημείο του πλέγματος ~(x,\,y)~ και είναι πρόθυμος να περπατήσει κάποια απόσταση για να τον συναντήσει. Συγκεκριμένα, ο Mirko θα συναντήσει έναν δεδομένο φίλο σε κάποιο σημείο κιγκλίδας με απόσταση το πολύ P βήματα από το σπίτι αυτού του φίλου, με τον ~P~ να εξαρτάται από την τεμπελιά του συγκεκριμένου φίλου.
Αφού τελείωσε τη βόλτα του, ο Mirko θυμήθηκε τη σειρά με την οποία συναντήθηκε με τους φίλους του. Υπολογίσε τον ελάχιστο δυνατό αριθμό βημάτων που έπρεπε να κάνει ο Mirko κατά τη διάρκεια της βόλτας του. Η αρχική και τελική θέση του Mirko δεν είναι γνωστές.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει τον θετικό ακέραιο ~N (2 \le N \le 200\,000)~, τον αριθμό των φίλων του Mirko.
Κάθε μία από τις ακόλουθες ~N~ γραμμές περιέχει τρεις ακέραιους αριθμούς που περιγράφουν έναν φίλο: ~x~, ~y~ και ~P (0 \le x, y, P \le 200\,000)~.Οι φίλοι δίνονται με τη σειρά που τους έχει γνωρίσει ο Mirko..

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο ελάχιστο δυνατό αριθμό βημάτων που o Mirko έπρεπε να κάνει.

Βαθμολογία

Σε δεδομένα δοκιμής συνολικής αξίας ~30~ πόντων, όλοι οι αριθμοί στην είσοδο (συμπεριλαμβανομένου του ~N~) θα είναι το πολύ ~200~. Σε δεδομένα δοκιμής αξίας επιπλέον ~30~ πόντων, κανένας φίλος δεν θα έχει ~P~ μεγαλύτερο από ~10~.

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

input

3
3 10 2
8 4 2
2 5 2

output

4

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

Ο Mirko θα μπορούσε να ξεκινήσει στις συντεταγμένες ~(4,\,8)~, συνάντησε τον πρώτο του φίλο, έκανε δύο βήματα και έφτασε στο σημείο ~(6,\,6)~, συνάντησε τον δεύτερο του φίλο, έκανε δύο βήματα μέχρι το σημείο ~(4,\,5)~ και συνάντησε τον τρίτο φίλο εκεί.

input

4
3 3 5
7 11 5
20 0 10
30 18 3

output

19