Computer Purchase Return

Αφού σκεφτήκατε να αγοράσετε έναν ολοκαίνουργιο Atari ή υπολογιστή Commodore (βάσει της εκτενούς σας έρευνας στα τέλη Φεβρουαρίου), αποφασίζετε να αποκτήσετε την καλύτερη αξία για το δολάριο σας κατασκευάζοντας το δικό σας.

Ο υπολογιστής που πρόκειται να κατασκευάσετε αποτελείται από ~T~ (~1 \le T \le 5~) διαφορετικούς τύπους εξαρτημάτων. Ο υπολογιστής σας πρέπει να έχει ακριβώς ένα από κάθε τύπο εξαρτήματος.

Κάθε στοιχείο έχει ένα ακέραιο κόστος ~c_i~ (~1 \le c_i \le 3\,000~), μια ακέραια τιμή ~v_i~ (~1 \le v_i \le 3\,000~) και τύπο ~t_i~ (~1 \le t_i \le T~).

Το ηλεκτρονικό σας κατάστημα ανταλλακτικών υπολογιστών διαθέτει ~N~ διαφορετικά εξαρτήματα (~1 \le N \le 1\,000~) από τα οποία μπορείτε να επιλέξτε.

Για έναν δεδομένο προϋπολογισμό ~B~ (~1 \le B \le 3\,000~), μεγιστοποιήστε τη συνολική αξία των εξαρτημάτων στον υπολογιστή σας.

Εάν δεν μπορείτε να κατασκευάσετε έναν τέτοιο υπολογιστή, θα πρέπει να εκτυπώσετε -1.

Είσοδος

Η πρώτη γραμμή περιέχει το ~T~, τον αριθμό των τύπων εξαρτημάτων που απαιτεί ο υπολογιστής σας. Η επόμενη γραμμή περιέχει τον αριθμό ~N~, ακολουθούμενο από ~N~ γραμμές με τρεις ακέραιους, που αντιπροσωπεύουν το ~c_i~, ~v_i~ κσι ~t_i~, χωρισμένα με ένα κενό. Η τελευταία γραμμή της εισόδου είναι ο προϋπολογισμός ~B~.

Έξοδος

Εκτυπώστε την αξία του υπολογιστή με την μέγιστη αξία που μπορείτε να κατασκευάσετε που κοστίζει το πολύ ~B~ ή -1 αν δεν μπορείτε να κατασκευάσετε έναν υπολογιστή.

Παράδειγμα

input

2
5
10 6 1
5 7 1
6 10 2
1 5 1
11 11 2
16

output

18

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

Προσέξτε ότι αν διαλέξετε τα εξαρτήματα με κόστος ~11~ και ~5~ κατασκευάζετε έναν υπολογιστή με αξία ~18~. Κανένας άλλος συνδυασμός εξαρτημάτων δεν έχει μεγαλύτερη αξία.