Course Overload

Η Alex είναι μια νέα φοιτήτρια στο Πανεπιστήμιο Consec και πρέπει να επιλέξει ποια μαθήματα θα παρακολουθήσει.

Έχει στη διάθεσή της ~N~ μαθήματα για να επιλέξει. Οι διαλέξεις του ~i~-οστού μαθήματος πραγματοποιούνται καθημερινά από την ημέρα ~s_i~ έως και την ημέρα ~f_i~ (συμπεριλαμβανομένων), αρχίζοντας την ώρα ~b_i~ και τελειώνοντας την ώρα ~e_i~ (συμπεριλαμβανομένων), όπου οι ώρες των διαλέξεων δίνονται σε λεπτά από την αρχή της σχολικής ημέρας.

Η Alex πρέπει να παρακολουθεί όλες τις διαλέξεις. Αν δύο μαθήματα έχουν επικαλυπτόμενες διαλέξεις, δεν μπορεί να επιλέξει και τα δύο. Επιπλέον, ορισμένα μαθήματα είναι υποχρεωτικά για την αποφοίτηση και πρέπει οπωσδήποτε να επιλεγούν. Επίσης, η Alex πρέπει να επιλέξει τουλάχιστον ~M~ μαθήματα για να μπορέσει να αποφοιτήσει.

Η Alex αποδίδει μια τιμή ~v_i~ σε κάθε λεπτό ενός μαθήματος, η οποία εκφράζει πόσο επιθυμεί να παρακολουθήσει το συγκεκριμένο μάθημα. Όσο πιο πολύτιμο θεωρεί ένα λεπτό ενός μαθήματος, τόσο μεγαλύτερη είναι η τιμή ~v_i~ που του αποδίδει.

Βοηθήστε την Alex να μεγιστοποιήσει τη συνολική αξία των μαθημάτων που θα επιλέξει!

Είσοδος

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

Οι επόμενες ~N~ γραμμές θα περιέχουν από έξι ακέραιους αριθμούς η καθεμία: ~s_i~, ~f_i~, ~b_i~, ~e_i~, ~m_i~ και ~v_i~ (~1 \le s_i \le f_i \le 1000~, ~1 \le b_i \le e_i \le 1000~, ~1 \le v_i \le 1000~, ~m_i \in \{0, 1\}~).

Αν ~m_i = 0~, το ~i~-οστό μάθημα είναι προαιρετικό, ενώ αν ~m_i = 1~, το ~i~-οστό μάθημα είναι υποχρεωτικό.

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι ~25~ διαθέσιμοι βαθμοί:

Βαθμοί	Όρια του ~N~	Επιπλέον περιορισμοί
~2~	~1 \le N \le 2~	Κανένας επιπλέον περιορισμός.
~3~	~1 \le N \le 20~	Για κάθε ~i~, ισχύει ~m_i = 1~.
~5~	~1 \le N \le 20~	Για κάθε ~i~, ισχύει ~s_i = f_i~.
~10~	~1 \le N \le 15~	Κανένας επιπλέον περιορισμός.
~5~	~1 \le N \le 20~	Κανένας επιπλέον περιορισμός.

Έξοδος

Αν η Alex δεν μπορεί να αποφοιτήσει επειδή δεν είναι δυνατό να επιλεγούν όλα τα υποχρεωτικά μαθήματα ή/και δεν είναι δυνατό να επιλεγεί ο απαιτούμενος συνολικός αριθμός μαθημάτων, εκτυπώστε ~-1~.

Διαφορετικά, εκτυπώστε έναν ακέραιο αριθμό: τη μέγιστη συνολική αξία των μαθημάτων που μπορεί να συμπεριλάβει στο πρόγραμμά της η Alex.

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

input

5 1
1 4 1 50 0 4
1 3 61 150 0 5
1 2 31 60 1 7
2 2 41 50 0 3
1 3 61 150 0 2

output

1770

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

Επειδή το μάθημα ~3~ είναι υποχρεωτικό, πρέπει οπωσδήποτε να επιλεγεί. Το μάθημα ~3~ συγκρούεται με τα μαθήματα ~1~ και ~4~, επομένως αυτά δεν μπορούν να επιλεγούν.

Τα μαθήματα ~2~ και ~5~ δεν συγκρούονται με το μάθημα ~3~, αλλά συγκρούονται μεταξύ τους, οπότε μπορεί να επιλεγεί μόνο ένα από τα δύο. Τα μαθήματα ~2~ και ~5~ έχουν την ίδια συνολική διάρκεια διαλέξεων, αλλά το μάθημα ~2~ έχει μεγαλύτερη συνολική αξία, επομένως είναι προτιμότερο να επιλεγεί το μάθημα ~2~ αντί για το μάθημα ~5~.

Επιλέγοντας το δεύτερο και το τρίτο μάθημα, η συνολική αξία όλων των μαθημάτων είναι ~3 \times 90 \times 5 + 2 \times 30 \times 7 = 1770~.