ΕΠΙΣΚΕΥΗ ΔΡΟΜΟΥ

Σε έναν επαρχιακό δρόμο πρόκειται να γίνει ένας αγώνας σκυταλοδρομίας (ίσως αυτός του προβλήματος της Β' φάσης του γυμνασίου, που όμως δε χρειάζεται να διαβάσετε για να λύσετε αυτό το πρόβλημα). Ο δρόμος όμως έχει τα κακά του τα χάλια, το οδόστρωμα έχει φθαρεί και χρειάζεται άμεσα επισκευή. Ο δήμαρχος κάνει αμέσως διαγωνισμό για την επισκευή και μαζεύει προσφορές από συνεργεία που προτίθενται να επισκευάσουν τμήματα του δρόμου. Κάθε προσφορά είναι μία τριάδα (~X_i~, ~L_i~, ~C_i~) που σημαίνει ότι κάποιο συνεργείο προτίθεται να επισκευάσει το τμήμα του δρόμου που αρχίζει στο χιλιόμετρο ~X_i~ και έχει μήκος ~L_i~, με κόστος ~C_i~.

Βοηθήστε τον δήμαρχο να βρει το ελάχιστο κόστος που απαιτείται για να επισκευάσει οποιοδήποτε τμήμα του δρόμου. Προσέξτε ότι για να επισκευαστεί ένα τμήμα του δρόμου που αρχίζει στο χιλιόμετρο ~Y_j~ και έχει μήκος ~K_j~, o δήμαρχος πρέπει να επιλέξει ένα υποσύνολο των προσφορών που συνολικά να καλύπτουν όλο αυτό το τμήμα του δρόμου. Ενδέχεται κάποια μέρη του τμήματος αυτού να καλύπτονται από περισσότερες προσφορές. Επίσης, ενδέχεται κάποιες από τις προσφορές που θα επιλέξει να επισκευάζουν και μέρη του δρόμου εκτός του εν λόγω τμήματος.

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του IOI (PASCAL, C, C++, Java) το οποίο θα διαβάζει τις προσφορές για την επισκευή τμημάτων του δρόμου και θα απαντά σε έναν αριθμό ερωτημάτων της μορφής: ποιο είναι το ελάχιστο κόστος για την επισκευή κάποιου συγκεκριμένου τμήματος του δρόμου. Κάθε ερώτημα πρέπει να απαντάται ανεξάρτητα από τα υπόλοιπα ερωτήματα.

Αρχεία εισόδου:

Τα αρχεία εισόδου με όνομα roadfix.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή της εισόδου θα περιέχει δύο φυσικούς αριθμούς N, Μ, χωρισμένους με ένα κενό διάστημα: το πλήθος των προσφορών και το πλήθος των ερωτημάτων που θα γίνουν.

Κάθε μία από τις επόμενες Ν γραμμές περιγράφει μία προσφορά: περιέχει τρεις ακέραιους αριθμούς ~X_i~ ~L_i~ και ~C_i~, χωρισμένους ανά δύο με ένα κενό διάστημα.

Κάθε μία από τις επόμενες M γραμμές περιγράφει ένα ερώτημα: περιέχει δύο ακέραιους αριθμούς ~Y_j~ και ~K_j~, χωρισμένους μεταξύ τους ένα κενό διάστημα.

Αρχεία εξόδου:

Τα αρχεία εξόδου με όνομα roadfix.out είναι αρχεία κειμένου με την εξής δομή. Περιέχουν ακριβώς Μ γραμμές που κάθε μία περιέχει έναν ακέραιο αριθμό: το ελάχιστο κόστος για την επισκευή του τμήματος του δρόμου του αντίστοιχου ερωτήματος, κατά σειρά. Αν η επισκευή του τμήματος δεν είναι εφικτή, η γραμμή που αντιστοιχεί στο ερώτημα πρέπει να περιέχει τον αριθμό ~-1~.

Περιορισμοί:

• ~2~ ~\le~ ~N~ ~\le~ ~10~.~000~
• ~1~ ~\le~ ~M~ ~\le~ ~10~
• ~1~ ~\le~ ~X_i~ ~<~ ~X_i~ + ~L_i~ ~\le~ ~1~.~000~.~000~.~000~
• ~1~ ~\le~ ~C_i~ ~\le~ ~10~.~000~
• ~1~ ~\le~ ~Y_j~ ~<~ ~Y_j~ + ~K_j~ ~\le~ ~1~.~000~.~000~.~000~

Παράδειγμα αρχείων εισόδου-εξόδου:

STDIN (roadfix.in)

5 3
30 45 20
40 40 30
60 35 5
20 25 10
90 10 15
20 80
50 30
10 30

STDOUT (roadfix.out)

50
25
-1

input

2 8
4 2 100
6 2 200
5 2
4 1
4 2
4 3
4 4
5 3
6 2
7 1

output

300
100
100
300
300
300
200
200

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

Υπάρχουν πέντε προσφορές, οι οποίες καλύπτουν τα τμήματα του δρόμου που φαίνονται στο παρακάτω σχήμα.

Για το πρώτο ερώτημα, το τμήμα του δρόμου από το ~20~ μέχρι το ~100~ (μήκους ~80~) μπορεί να επισκευαστεί με το ελάχιστο κόστος επιλέγοντας τις προσφορές ~10~ + ~20~ + ~5~ + ~15~ = ~50~. (Ο δήμαρχος μπορεί επίσης να επιλέξει την προσφορά ~30~ αντί της ~20~, αλλά το κόστος τότε θα ήταν μεγαλύτερο.)

Για το δεύτερο ερώτημα, το ελάχιστο κόστος είναι ~20~ + ~5~ = ~25~.

Για το τρίτο ερώτημα, το τμήμα του δρόμου από το ~10~ μέχρι το ~20~ δεν επισκευάζεται με καμία από τις προσφορές, άρα η απάντηση είναι ~-1~.

Παρατηρήσεις:

Μορφοποίηση: Στην είσοδο αλλά και στην έξοδο, κάθε γραμμή τερματίζει με έναν χαρακτήρα newline.

Μέγιστος χρόνος εκτέλεσης: 1 sec.
Μέγιστη διαθέσιμη μνήμη: 64 MB.
Επικεφαλίδες στον πηγαίο κώδικα: Στην αρχή του πηγαίου κώδικά σας, θα πρέπει να χρησιμοποιήσετε τις παρακάτω επικεφαλίδες.

(* USER: username
LANG: PASCAL
TASK: roadfix *)

για κώδικα σε PASCAL

/* USER: username
LANG: C
TASK: roadfix */

για κώδικα σε C

/* USER: username
LANG: C++
TASK: roadfix */

για κώδικα σε C++

/* USER: username
LANG: Java
TASK: roadfix */

για κώδικα σε Java

# USER: username
# LANG: Python
# TASK: roadfix

για κώδικα σε Python