Shopping Deals

Κάνετε αγορές σε ένα κατάστημα που πουλά συνολικά ~M~ προϊόντα. Η διάταξη του καταστήματος μπορεί να μοντελοποιηθεί ως ένα δισδιάστατο επίπεδο, όπου το ~i~-οστό προϊόν βρίσκεται στο σημείο ~(x_i, y_i)~ και έχει τιμή ~p_i~.

Το κατάστημα προσφέρει ~N~ προσφορές. Η ~i~-οστή προσφορά καθορίζεται από ένα σημείο ~(a_i, b_i)~ και, πληρώνοντας ~c_i~, μπορείτε να αποκτήσετε ένα από κάθε προϊόν που βρίσκεται σε μία ακριβώς από τις ακόλουθες τέσσερις περιοχές της επιλογής σας:

• Την περιοχή των σημείων ~(x, y)~ για τα οποία ισχύει ~x \le a_i~ και ~y \le b_i~.

• Την περιοχή των σημείων ~(x, y)~ για τα οποία ισχύει ~x \le a_i~ και ~y \ge b_i~.

• Την περιοχή των σημείων ~(x, y)~ για τα οποία ισχύει ~x \ge a_i~ και ~y \le b_i~.

• Την περιοχή των σημείων ~(x, y)~ για τα οποία ισχύει ~x \ge a_i~ και ~y \ge b_i~.

Κάθε προσφορά μπορεί να χρησιμοποιηθεί το πολύ μία φορά. Μπορείτε επίσης να αγοράσετε προϊόντα μεμονωμένα, πληρώνοντας την αντίστοιχη τιμή ~p_i~.

Θέλετε να αποκτήσετε τουλάχιστον ένα από κάθε προϊόν του καταστήματος. Βρείτε το ελάχιστο συνολικό κόστος που πρέπει να πληρώσετε για να το πετύχετε.

Είσοδος

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

Οι επόμενες ~N~ γραμμές θα περιέχουν από τρεις ακέραιους αριθμούς ~a_i~, ~b_i~ και ~c_i~, χωρισμένους με κενά (~-10^9 \le a_i, b_i \le 10^9~, ~1 \le c_i \le 10^9~).

Οι επόμενες ~M~ γραμμές θα περιέχουν από τρεις ακέραιους αριθμούς ~x_i~, ~y_i~ και ~p_i~, χωρισμένους με κενά (~-10^9 \le x_i, y_i \le 10^9~, ~1 \le p_i \le 10^9~).

Βαθμολογία

Βαθμοί	Όρια	Επιπλέον περιορισμοί
~1~	~1 \le N \le 8~, ~1 \le M \le 20~	Κανένας επιπλέον περιορισμός.
~3~	~1 \le N \le 70~, ~1 \le M \le 20~	Κανένας επιπλέον περιορισμός.
~3~	~1 \le N \le 70~, ~1 \le M \le 70~	Κανένας επιπλέον περιορισμός.
~4~	~1 \le N \le 100~, ~1 \le M \le 100.000~	Κανένα ζεύγος σημείων ~(a_i, b_i)~ ή ~(x_j, y_j)~ δεν έχει την ίδια συντεταγμένη ~x~ ή ~y~.
~2~	~1 \le N \le 100~, ~1 \le M \le 100.000~	Κανένας επιπλέον περιορισμός.
~8~	~1 \le N \le 1000~, ~1 \le M \le 100.000~	Κανένα ζεύγος σημείων ~(a_i, b_i)~ ή ~(x_j, y_j)~ δεν έχει την ίδια συντεταγμένη ~x~ ή ~y~.
~4~	~1 \le N \le 1000~, ~1 \le M \le 100.000~	Κανένας επιπλέον περιορισμός.

Έξοδος

Να εκτυπώσετε σε μία γραμμή το ελάχιστο συνολικό κόστος που πρέπει να πληρώσετε για να αποκτήσετε τουλάχιστον ένα από κάθε προϊόν.

Παράδειγμα

input

2 4
1 1 3
3 3 13
0 0 2
0 2 5
2 0 4
2 2 3

output

12

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

Χρησιμοποιήστε την πρώτη προσφορά στην περιοχή ~\{(x, y) \mid x \le 1, y \ge 1\}~ για να αποκτήσετε το δεύτερο προϊόν.

Στη συνέχεια, αγοράστε τα προϊόντα ~1~, ~3~ και ~4~ μεμονωμένα. Το συνολικό κόστος είναι ~3 + (2 + 4 + 3) = 12~.