Lunch Concert

Είναι ώρα για μεσημεριανό γεύμα στο σχολείο σας! Οι ~N~ φίλοι σας στέκονται όλοι σε ένα μακρύ γήπεδο, όπως συνήθως. Το γήπεδο μπορεί να αναπαρασταθεί με μια αριθμητική γραμμή, με τον ~i~-οστό φίλο να βρίσκεται αρχικά σε θέση ~P_{i}~ μέτρα επάνω σε αυτήν. Ο ~i~-οστός φίλος σας μπορεί να περπατήσει προς οποιαδήποτε κατεύθυνση κατά μήκος του γηπέδου με ρυθμό ένα μέτρο ανά ~W_{i}~ δευτερόλεπτα, και η ακοή του είναι αρκετά καλή ώστε να μπορεί να ακούσει μουσική μέχρι και ~D_{i}~ μέτρα μακριά από τη θέση του. Μπορεί πολλοί μαθητές να καταλάβουν τις ίδιες θέσεις στο γήπεδο, τόσο αρχικά όσο και μετά τη μετακίνησή τους.

Θα διοργανώσετε μια μικρή συναυλία σε κάποια θέση ~c~ μέτρα κατά μήκος του γηπέδου (όπου ~c~ είναι οποιοσδήποτε ακέραιος της επιλογής σας) και θα στείλετε μήνυμα σε όλους τους φίλους σας γι' αυτήν. Μόλις το κάνετε, ο καθένας από αυτούς θα περπατήσει κατά μήκος του γηπέδου για το ελάχιστο χρονικό διάστημα ώστε να καταλήξει να είναι σε θέση να ακούσει τη συναυλία σας (με άλλα λόγια, έτσι ώστε κάθε φίλος ~i~ να καταλήξει σε απόσταση εντός των ~D_{i}~ μονάδων από το ~c~).

Θα θέλατε να επιλέξετε το ~c~ με τέτοιο τρόπο που να ελαχιστοποιείτε το άθροισμα των χρόνων που θα περπατήσουν όλοι οι ~N~ φίλοι σας. Ποιο είναι αυτό το ελάχιστο άθροισμα (σε δευτερόλεπτα); Σημειώστε ότι το αποτέλεσμα μπορεί να μην χωράει μέσα σε έναν ακέραιο αριθμό 32 bit.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τον ~N~.

Οι επόμενες ~N~ γραμμές θα περιέχουν τρεις ακέραιους αριθμούς, ~P_{i}~, ~W_{i}~ και ~D_{i}\;(1 \le i \le N)~.

Για ~4~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 2000~, ~0 \le P_{i} \le 2000~, ~1 \le W_{i} \le 1000~ και ~0 \le D_{i} \le 2000~.

Για επιπλέον ~9~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 200\;000~, ~0 \le P_{i} \le 1\;000\;000~, ~1 \le W_{i} \le 1000~ και ~0 \le D_{i} \le 1\;000\;000~.

Για επιπλέον ~2~ από τους ~15~ διαθέσιμους βαθμούς, ~1 \le N \le 200\;000~, ~0 \le P_{i} \le 1\;000\;000\;000~, ~1 \le W_{i} \le 1000~ και ~0 \le D_{i} \le 1\;000\;000\;000~.

Έξοδος

Εξάγετε έναν ακέραιο αριθμό που θα είναι το ελάχιστο δυνατό άθροισμα των χρόνων μετακίνησης (σε δευτερόλεπτα) ώστε όλοι οι ~N~ φίλοι σας να είναι σε θέση να ακούσουν τη συναυλία σας.

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

input

1
0 1000 0

output

0

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

Αν επιλέξετε ~c = 0~, ο μοναδικός σας φίλος δεν θα χρειαστεί να περπατήσει καθόλου για να μπορεί να ακούσει.

input

2
10 4 3
20 4 2

output

20

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

Μια πιθανή βέλτιστη επιλογή για το ~c~ είναι ~14~, όπου θα χρειαζόταν ο πρώτος σας φίλος να περπατήσει μέχρι τη θέση ~11~ (που απαιτεί ~4 \times 1 = 4~ δευτερόλεπτα) και ο δεύτερος φίλος σας να περπατήσει ως τη θέση ~16~ (που απαιτεί ~4 \times 4 = 16~ δευτερόλεπτα), δηλαδή συνολικά ~20~ δευτερόλεπτα.

input

3
6 8 3
1 4 1
14 5 2

output

43