An có ~n~ trò chơi. Để có thể chơi trò chơi thứ ~i~, trước hết An phải dành ~p_i~ phút để học luật chơi của trò đó. Sau khi đã học xong, An có thể chơi trò chơi này nhiều lần. Mỗi lần chơi trò chơi thứ ~i~ tốn ~t_i~ phút và nhận được ~o_i~ điểm.

Trong tổng cộng không quá ~d~ phút, An có thể tùy ý học luật một số trò chơi và chơi các trò đã học.

Yêu cầu

Tìm tổng điểm lớn nhất mà An có thể đạt được trong không quá ~d~ phút.

Dữ liệu

Dữ liệu vào từ ~stdin~ gồm:

• Dòng đầu chứa hai số nguyên ~n~ và ~d~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~p_i~, ~t_i~, ~o_i~.

Kết quả

Ghi ra ~stdout~ một số nguyên duy nhất là tổng điểm lớn nhất có thể đạt được.

Ví dụ

Ví dụ 1

Input

3 10
1 1 1
3 2 3
2 3 5

Output

11

Giải thích

Ví dụ 1

Một phương án đạt ~11~ điểm là:

• Dành ~1~ phút để học trò chơi thứ ~1~, sau đó chơi trò này ~1~ lần.
• Dành ~2~ phút để học trò chơi thứ ~3~.
• Trong ~6~ phút còn lại, chơi trò thứ ~3~ đúng ~2~ lần.

Tổng điểm nhận được là ~1 + 5 + 5 = 11~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n, d \le 5000~
• ~0 \le p_i \le 5000~
• ~1 \le t_i \le 5000~
• ~1 \le o_i \le 10^9~

Chấm điểm

• Subtask ~1~ ~(14\%):~ ~n = 1~
• Subtask ~2~ ~(24\%):~ ~n \le 10~
• Subtask ~3~ ~(26\%):~ ~p_i = 0~ với mọi ~i~
• Subtask ~4~ ~(36\%):~ Không có ràng buộc thêm