Βοηθώντας τα αγροτικά όνειρα του Μήτσου

Εκφώνηση

Ο Μήτσος, συνειδητοποιώντας ότι το competitive programming δεν είναι ιδιαίτερα κερδοφόρο, αποφάσισε να επιστρέψει στα πάτρια εδάφη και να ασχοληθεί με τη γαλακτοπαραγωγή. Έχει όμως ένα βασικό πρόβλημα. Με το πιο ζεστό καλοκαίρι της ιστορίας να είναι καθ' οδόν, χρειάζεται έναν τρόπο για να δροσίσει τις αγελάδες του. Έτσι, αποφασίζει να επενδύσει σε κάποια κλιματιστικά.

Ο Μήτσος έχει N αγελάδες (1 ≤ N ≤ 20) που ζουν σε έναν αχυρώνα, ο οποίος περιέχει μια σειρά από θέσεις που είναι αριθμημένες από 1 έως 100. Η αγελάδα i καταλαμβάνει μια αδιάκοπη σειρά από αυτές τις θέσεις, ξεκινώντας από τη θέση sᵢ και τελειώνοντας στη θέση tᵢ. Οι σειρές των θέσεων που καταλαμβάνονται από διαφορετικές αγελάδες δεν επικαλύπτονται.

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

Ο αχυρώνας περιέχει M κλιματιστικά (1 ≤ M ≤ 10), αριθμημένα από 1 έως M. Το i-οστό κλιματιστικό έχει κόστος λειτουργίας mᵢ μονάδες χρημάτων (1 ≤ mᵢ ≤ 1000) και ψύχει τη σειρά των θέσεων που ξεκινούν από τη θέση aᵢ και τελειώνουν στη θέση bᵢ. Αν λειτουργεί, το i-οστό κλιματιστικό μειώνει τη θερμοκρασία όλων των θέσεων σε αυτή την περιοχή κατά pᵢ μονάδες (1 ≤ pᵢ ≤ 10⁶). Οι περιοχές που καλύπτονται από διαφορετικά κλιματιστικά μπορεί να επικαλύπτονται.

Η λειτουργία μιας φάρμας δεν είναι εύκολη υπόθεση, οπότε ο Μήτσος έχει περιορισμένο προϋπολογισμό. Παρακαλείστε να προσδιορίσετε το ελάχιστο ποσό χρημάτων που χρειάζεται να ξοδέψει για να λειτουργήσει αρκετά κλιματιστικά ώστε να διατηρήσει όλες τις αγελάδες του άνετες. Είναι εγγυημένο ότι αν ο Μήτσος χρησιμοποιήσει όλα τα κλιματιστικά, τότε όλες οι αγελάδες θα είναι ικανοποιημένες.

Μορφή Εισόδου (input από το τερματικό / stdin):

Η πρώτη γραμμή της εισόδου περιέχει τους αριθμούς N και M. Οι επόμενες N γραμμές περιγράφουν τις αγελάδες. Η i-οστή από αυτές τις γραμμές περιέχει τους αριθμούς sᵢ, tᵢ, cᵢ. Οι επόμενες M γραμμές περιγράφουν τα κλιματιστικά. Η i-οστή από αυτές τις γραμμές περιέχει τους αριθμούς aᵢ, bᵢ, pᵢ, mᵢ. Για κάθε είσοδο, εκτός από το δείγμα, μπορείτε να υποθέσετε ότι M = 10.

Μορφή Εξόδου (print στο τερματικό / stdout):

Εκτυπώστε έναν ακέραιο αριθμό που δηλώνει το ελάχιστο ποσό χρημάτων που χρειάζεται να ξοδέψει ο Μήτσος για να λειτουργήσει αρκετά κλιματιστικά ώστε να ικανοποιήσει όλες τις αγελάδες.

Παράδειγμα

Δείγμα Εισόδου:

2 4
1 5 2
7 9 3
2 9 2 3
1 6 2 8
1 2 4 2
6 9 1 5

Δείγμα Εξόδου:

10

Επεξήγηση:

Μία πιθανή λύση που οδηγεί στο ελάχιστο κόστος είναι να επιλεγούν τα κλιματιστικά που ψύχουν τα διαστήματα [2,9], [1,2] και [6,9], με συνολικό κόστος 3 + 2 + 5 = 10. Δημιουργοί προβλήματος: Aryansh Shrivastava και Eric Hsu