Splitting Hares

Όπως γνωρίζετε, μερικά κουνελάκια είναι καλά κουνελάκια, και μερικά κουνελάκια είναι κακά κουνελάκια.

Σας δίνεται η τοποθεσία όλων των κουνελιών και το βάρος τους σε «καλοσύνη» (ένας θετικός ακέραιος για τα καλά κουνελάκια και ένας αρνητικός ακέραιος αριθμός για τα κακά κουνελάκια). Δεν υπάρχουν δύο κουνελάκια στην ίδια τοποθεσία. Χωρίστε τα σε δύο ομάδες χρησιμοποιώντας μια ευθεία γραμμή έτσι ώστε το άθροισμα της «καλοσύνης» των κουνελιώ στη μία πλευρά της γραμμής να είναι όσο το δυνατόν μεγαλύτερη. Ένα λαγουδάκι στη γραμμή υπολογίζεται στο άθροισμα του βάρους και στις δύο πλευρές της γραμμής.

Είσοδος

Η πρώτη γραμμή περιέχει ~N~ (~2 \le N \le 4\,000~), τον αριθμό από λαγουδάκια. Οι επόμενες ~N~ γραμμές περιέχουν τρεις, χωρισμένους με κενό, ακέραιους: ~x_i~ ~y_i~ ~w_i~, που υποδεικνύουν ότι στο σημείο (~x_i~, ~y_i~) υπάρχει ένα λαγουδάκι με βάρος «καλοσύνης» ~w_i~ (~- 1\,000\,000 \le x_i \le 1\,000\,000~, ~- 1\,000\,000 \le y_i \le 1\,000\,000~, ~- 10\,000 \le w_i \le 10\,000~). Οι τοποθεσίες (~x_i~, ~y_i~) θα είναι διακριτές (δηλαδή, δεν υπάρχει άλλο ~j \ne i~ τέτοιο ώστε (~x_i~, ~y_i~) = (~x_j~, ~y_j~)).

Βαθμολογία

Για ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~N \le 200~ και δεν υπάρχουν τρεις τοποθεσίες συγγραμμικές.

Για επιπλέον ~10~ από τους ~25~ διαθέσιμους βαθμούς, δεν υπάρχουν τρεις τοποθεσίες συγγραμμικές.

Έξοδος

Εκτυπώστε το μέγιστο άθροισμα βαρών που είναι εφικτό σχεδιάζοντας μία ευθεία γραμμή και διαλέγοντας όλα τα λαγουδάκια που βρίσκονται από τη μία πλευρά της γραμμής.

Παράδειγμα

input

6
1 8 4
1 4 6
7 7 2
4 10 -3
4 6 -9
4 2 8

output

18

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

Πάρτε τα κουνελάκια με βάρος καλοσύνης ~4~, ~6~ και ~8~, που βρίσκονται στην "αριστερή" πλευρά της γραμμής, όπως φαίνεται στο παρακάτω διάγραμμα: