Ιχθυοτροφείο Γατόψαρων

Η Bu Dengklek έχει ένα ιχθυοτροφείο με γατόψαρα. Το ιχθυοτροφείο της βρίσκεται σε μία λίμνη που αποτελείται από ένα ~N \times N ~ πλέγμα κελιών. Κάθε κελί έχει σχήμα τετραγώνου με ίδιο μέγεθος. Οι στήλες του πλέγματος αριθμούνται από ~0~ έως ~N - 1~ από δυτικά προς ανατολικά και οι σειρές αριθμούνται από ~0~ έως ~N - 1~ από νότια προς βόρεια. Αναφερόμαστε στο κελί που βρίσκεται στη στήλη ~c~ και στη γραμμή ~r~ του πλέγματος (~0 \le c \le N - 1~, ~0 \le r \le N - 1~) ως κελί ~(c, r) ~.

Στη λίμνη υπάρχουν ~M~ γατόψαρα, αριθμημένα από ~0~ έως ~M - 1~, που βρίσκονται σε διαφορετικά κελιά. Για κάθε ~i~, τέτοιο ώστε ~0 \le i \le M - 1~, το γατόψαρο ~i~ βρίσκεται στο κελί ~(X[i], Y[i])~ και ζυγίζει ~W[i]~ γραμμάρια.

Η Bu Dengklek θέλει να κατασκευάσει μερικές προβλήτες για να πιάσει γατόψαρα. Μια προβλήτα που βρίσκεται στη στήλη ~c~ μήκους ~k~ (για οποιoδήποτε ~0 \le c \le N - 1~ και ~1 \le k \le N~) είναι ένα ορθογώνιο που επεκτείνεται από τη γραμμή ~0~ μέχρι και τη γραμμή ~k - 1~, καλύπτοντας τα κελιά ~(c, 0), (c, 1), \ldots, (c, k - 1)~. Για κάθε στήλη, η Bu Dengklek μπορεί να επιλέξει, είτε να κατασκευάσει μια προβλήτα κάποιου μήκους της επιλογής του, είτε να μην κατασκευάσει προβλήτα.

Το γατόψαρο ~i~ (για κάθε ~i~ τέτοιο ώστε ~0 \le i \le M - 1~) μπορεί να αλιευθεί εάν υπάρχει προβλήτα ακριβώς στα δυτικά ή ανατολικά του και δεν υπάρχει προβλήτα που να καλύπτει το δικό του κελί. Δηλαδή, αν

• τουλάχιστον ένα από τα κελιά ~(X[i] - 1, Y[i])~ ή ~(X[i] + 1, Y[i])~ καλύπτεται από προβλήτα, και
• δεν υπάρχει προβλήτα που να καλύπτει το κελί ~(X[i], Y[i])~.

Για παράδειγμα, θεωρείστε μια λίμνη μεγέθους ~N = 5~ με ~M = 4~ γατόψαρα:

• Το Γατόψαρο ~0~ βρίσκεται στο κελί ~(0, 2)~ και ζυγίζει ~5~ γραμμάρια.
• Το Γατόψαρο ~1~ βρίσκεται στο κελί ~(1, 1)~ και ζυγίζει ~2~ γραμμάρια.
• Το Γατόψαρο ~2~ βρίσκεται στο κελί ~(4, 4)~ και ζυγίζει ~1~ γραμμάριο.
• Το Γατόψαρο ~3~ βρίσκεται στο κελί ~(3, 3)~ και ζυγίζει ~3~ γραμμάρια.

Ένας τρόπος με τον οποίο η Bu Dengklek μπορεί να κατασκευάσει τις προβλήτες είναι ο εξής:

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

Η Bu Dengklek θα ήθελε να χτίσει προβλήτες έτσι ώστε το συνολικό βάρος των γατόψαρων που μπορεί να πιάσει να είναι όσο το δυνατόν μεγαλύτερο. Ο στόχος σας είναι να βρείτε το μέγιστο συνολικό βάρος γατόψαρων που μπορεί να πιάσει η Bu Dengklek αφού κατασκευάσει τις προβλήτες.

Λεπτομέρειες Υλοποίησης

Θα πρέπει να υλοποιήσετε την ακόλουθη διαδικασία:

int64 max_weights(int N, int M, int[] X, int[] Y, int[] W)

• ~N~: το μέγεθος της λίμνης.
• ~M~: ο αριθμός των γατόψαρων.
• ~X~, ~Y~: πίνακες μήκους ~M~ που περιγράφουν τις θέσεις των γατόψαρων.
• ~W~: πίνακας μήκους ~M~ που περιγράφει τα βάρη των γατόψαρων.
• Αυτή η διαδικασία πρέπει να επιστρέφει έναν ακέραιο αριθμό που αντιπροσωπεύει το μέγιστο συνολικό βάρος γατόψαρων που μπορεί να πιάσει η Bu Dengklek μετά που θα κατασκευάσει τις προβλήτες.
• Αυτή η διαδικασία καλείται ακριβώς μία φορά.

Παράδειγμα

Θεωρείστε την ακόλουθη κλήση:

max_weights(5, 4, [0, 1, 4, 3], [2, 1, 4, 3], [5, 2, 1, 3])

Αυτό το παράδειγμα απεικονίζεται παραπάνω, στην περιγραφή του προβλήματος.

Αφού κατασκευάσει τις προβλήτες όπως περιγράφεται, η Bu Dengklek μπορεί να πιάσει τα γατόψαρα ~0~ και ~3~, των οποίων το συνολικό βάρος είναι ~5 + 3 = 8~ γραμμάρια. Καθώς δεν υπάρχει τρόπος να κατασκευαστούν προβλήτες για να αλιευθούν γατόψαρα με συνολικό βάρος μεγαλύτερο των ~8~ γραμμάριων, η διαδικασία πρέπει να επιστρέψει ~8~.

Περιορισμοί

• ~2 \le N \le 100\;000~
• ~1 \le M \le 300\;000~
• ~0 \le X[i] \le N - 1~, ~0 \le Y[i] \le N - 1~ (για κάθε ~i~ τέτοιο ώστε ~0 \le i \le M - 1~)
• ~1 \le W[i] \le 10^9~ (για κάθε $i$ τέτοιο ώστε ~0 \le i \le M - 1~)
• Δεν υπάρχουν δύο γατόψαρα που να μοιράζονται το ίδιο κελί. Δηλαδή, ~X[i] \neq X[j]~ ή ~Y[i] \neq Y[j]~ (για κάθε ~i~ και ~j~ τέτοια ώστε ~0 \le i < j \le M - 1~).

Υποπροβλήματα

1. (3 βαθμοί) Το ~X[i]~ είναι άρτιος (για κάθε ~i~ τέτοιο ώστε ~0 \le i \le M - 1~)
2. (6 βαθμοί) ~X[i] \le 1~ (για κάθε ~i~ τέτοιο ώστε ~0 \le i \le M - 1~)
3. (9 βαθμοί) ~Y[i] = 0~ (για κάθε $i$ τέτοιο ώστε ~0 \le i \le M - 1~)
4. (14 βαθμοί) ~N \le 300~, ~Y[i] \le 8~ (για κάθε ~i~ τέτοιο ώστε ~0 \le i \le M - 1~)
5. (21 βαθμοί) ~N \le 300~
6. (17 βαθμοί) ~N \le 3000~
7. (14 βαθμοί) Υπάρχουν το πολύ ~2~ γατόψαρα σε κάθε στήλη.
8. (16 βαθμοί) Κανένας επιπλέον περιορισμός.

Υπόδειγμα βαθμολογητή

Ο βαθμολογητής διαβάζει την είσοδο στην ακόλουθη μορφή:

• γραμμή ~1~: ~N \; M~
• γραμμή ~2 + i~ (~0 \le i \le M - 1~): ~X[i] \; Y[i] \; W[i]~

Ο βαθμολογητής εκτυπώνει την απάντησή στην ακόλουθη μορφή:

• γραμμή ~1~: η επιστρεφόμενη τιμή της max_weights