30ος ΠΔΠ Καμπ (juniors)
Πίστες, κλειδιά κι αστέρια (pistes)

Παίζουμε ένα ηλεκτρονικό παιχνίδι που αποτελείται από \(N+1\) πίστες, αριθμημένες από \(0\) έως \(N\). Το παιχνίδι ξεκινάει υποχρεωτικά με την πίστα \(0\), που είναι εισαγωγική. Κάθε πίστα που ολοκληρώνουμε επιτυχώς, μας επιβραβεύει με κάποια «αστέρια», ανάλογα με τη δυσκολία της, και επίσης με κάποια «κλειδιά», πολλών διαφορετικών σχημάτων και μεγεθών, τα οποία μπορούμε να χρησιμοποιήσουμε για να ανοίξουμε και να παίξουμε άλλες, επόμενες πίστες. Προσέξτε ότι δεν χρειάζεται (και ίσως δεν είναι καν δυνατόν) να παίξουμε τις επόμενες πίστες κατ’ αριθμητική σειρά: για να ανοίξουμε και να παίξουμε μία πίστα πρέπει να διαθέτουμε το κατάλληλο σύνολο από κλειδιά. Επιπλέον, τα κλειδιά είναι μίας χρήσης: μόλις χρησιμοποιηθεί ένα κλειδί καταστρέφεται και δεν μπορεί να ξαναχρησιμοποιηθεί. Αφού λοιπόν παίξουμε την εισαγωγική πίστα, έχουμε δικαίωμα να επιλέξουμε ποια άλλη πίστα θα ανοίξουμε και θα παίξουμε, αρκεί φυσικά να μην την έχουμε ξαναπαίξει και να έχουμε στη διάθεσή μας όλα τα κλειδιά που χρειάζονται. Το παιχνίδι τελειώνει όταν δεν μπορούμε να παίξουμε καμία άλλη πίστα, είτε γιατί δεν έχει μείνει καμία, είτε γιατί δεν έχουμε διαθέσιμα κλειδιά για να ανοίξουμε όσες έχουν μείνει.

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

Δεδομένα εισόδου (pistes.in)

Η πρώτη γραμμή της εισόδου έχει τον αριθμό \(N\). Οι επόμενες \(N+1\) γραμμές περιέχουν τις περιγραφές των πιστών, ξεκινώντας από την \(0\) και προχωρώντας μέχρι αυτήν που έχει αύξοντα αριθμό \(N\). Κάθε τέτοια γραμμή αρχίζει με τρεις αριθμούς \(k_i\), \(r_i\) και \(s_i\) — το πλήθος των κλειδιών που απαιτούνται για το άνοιγμά της, το πλήθος των κλειδιών που αποκτούμε όταν την ολοκληρώσουμε, και το πλήθος των αστεριών που κερδίζουμε, αντίστοιχα — και συνεχίζουν με τους κωδικούς αριθμούς \(k_i + r_i\) κλειδιών. Θεωρήστε ότι τα κλειδιά είναι αριθμημένα με φυσικούς αριθμούς από \(1\) έως \(99.999\). Επίσης, θεωρήστε δεδομένο ότι η εισαγωγική πίστα δεν θα απαιτεί κανένα κλειδί (δηλαδή ότι το \(k_i\) της θα είναι μηδέν).

Δεδομένα εξόδου (pistes.out)

Η έξοδος πρέπει να περιέχει μία γραμμή με ακριβώς έναν φυσικό αριθμό: το μέγιστο δυνατό πλήθος αστεριών που μπορούμε να έχουμε κερδίσει στο τέλος του παιχνιδιού.

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

1^o

pistes.in	pistes.out
4 0 1 0 1 1 0 200 1 1 2 150 1 1 3 2 0 120 2 1 1 2 140 3 1 2	610

Εξήγηση: Στο πρώτο παράδειγμα, μπορεί κανείς να παίξει την εισαγωγική πίστα από την οποία αποκτά το κλειδί \(1\) αλλά κανένα αστέρι. Στη συνέχεια, μπορεί να χρησιμοποιήσει το κλειδί \(1\) για να παίξει την πίστα \(2\). Όταν τελειώσει, θα έχει \(150\) αστέρια και τα κλειδιά \(1\) και \(3\). Μετά, μπορεί να χρησιμοποιήσει το κλειδί \(3\) για να παίξει την πίστα \(4\), που θα του δώσει \(140\) αστέρια και τα κλειδιά \(1\) και \(2\) (άρα θα έχει τώρα \(290\) αστέρια και τα κλειδιά \(1\), \(1\) και \(2\) — δηλαδή δύο αντίτυπα του κλειδιού \(1\) και ένα αντίτυπο του κλειδιού \(1\)). Έπειτα, μπορεί να χρησιμοποιήσει τα κλειδιά \(2\) και \(1\) (τό ένα από τα δύο αντίτυπα που διαθέτει) για να παίξει την πίστα \(3\), που θα του δώσει \(120\) αστέρια και κανένα επιπλέον κλειδί. Τέλος, μπορεί να χρησιμοποιήσει το κλειδί \(1\) (το δεύτερο αντίτυπο) για να παίξει την πίστα \(1\), που θα του δώσει \(200\) αστέρια και κανένα επιπλέον κλειδί. Το παιχνίδι τελειώνει γιατί δεν υπάρχει άλλη πίστα που να μην έχει ανοίξει. Ο παίκτης έτσι θα έχει πάρει \(150+140+120+200 = 610\) αστέρια. Αυτό είναι και το μέγιστο εφικτό για αυτό το παράδειγμα.

2^o

pistes.in	pistes.out
5 0 3 10 1 3 1 2 1 100 1 3 2 3 2 900 1 1 2 5 3 2 2 200 5 1 1 3 1 2 130 2 3 5 2 2 120 3 2 1 1	440

Περιορισμοί

• \(1 \leq N \leq 10\).
• \(0 \leq k_i \leq 10\).
• \(0 \leq r_i \leq 10\).
• \(0 \leq s_i\).
• \(\sum s_i \leq 10^9\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: \(256\) MB.