Igre

Ο Kile επέστρεψε από μια έκθεση επιτραπέζιων παιχνιδιών. Έφερε στο σπίτι του ~n~ παιχνίδια. Πριν παίξει ένα παιχνίδι, είναι απαραίτητο να μάθει τους κανόνες του. Η εκμάθηση των κανόνων του ~i~-οστού παιχνιδιού απαιτεί ~p_i~ λεπτά. Μόλις μάθει τους κανόνες, μπορεί να παίξει το παιχνίδι. Το να παίξει το ~i~-οστό παιχνίδι απαιτεί ~t_i~ λεπτά. Κάθε παιχνίδι έχει επίσης τη δική του βαθμολογία, ~o_i~.

Τις επόμενες ημέρες, ο Kile έχει προγραμματίσει να αφιερώσει το πολύ ~d~ λεπτά στα επιτραπέζια παιχνίδια. Τον ενδιαφέρει να βρει το μέγιστο άθροισμα των βαθμολογιών των παιχνιδιών που μπορεί να παίξει. Κάθε παιχνίδι μπορεί να παιχτεί όσες φορές θέλουμε.

Είσοδος

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

Η ~i~-οστή από τις επόμενες ~n~ γραμμές περιέχει τους ακέραιους αριθμούς ~p_i~, ~t_i~ και ~o_i\;(0 \le p_i \le 5000,\; 1 \le t_i \le 5000,\;1 \le o_i \le 10^9)~, τον χρόνο που απαιτείται για να μάθει τους κανόνες, τον χρόνο που απαιτείται για να παίξει και τη βαθμολογία του ~i~-οστού παιχνιδιού.

Έξοδος

Στην πρώτη και μοναδική γραμμή, εκτύπωσε το μέγιστο άθροισμα των βαθμολογιών των παιχνιδιών που έπαιξε.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~6~	~n = 1~
~2~	~13~	~n \le 10~
~3~	~23~	~p_i = 0~ για κάθε ~i = 1, ..., n~
~4~	~28~	Κανένας επιπλέον περιορισμός

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

1ο

input

3 10
2 3 5
5 1 5
3 2 5

output

25

2ο

input

4 13
0 6 5
0 3 4
0 2 3
0 4 4

output

19

3ο

input

3 10
1 1 1
3 2 3
2 3 5

output

11

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

Ένας τρόπος για να επιτύχει συνολική βαθμολογία ~11~ είναι ο εξής: το πρώτο λεπτό, ο Kile μαθαίνει να παίζει το πρώτο παιχνίδι, και μετά το παίζει μια φορά. Στη συνέχεια, αφιερώνει δύο λεπτά για να μάθει να παίζει το τρίτο παιχνίδι, και στα τελευταία ~6~ λεπτά, το παίζει δύο φορές. Με αυτόν τον τρόπο, η συνολική βαθμολογία των παιχνιδιών που παίχτηκαν είναι: ~1 + 5 + 5 = 11~.