Board game thực chất là một loại hình trò chơi tập thể hấp dẫn, diễn ra trên bàn cờ với sự tham gia của nhiều người. Trong board game có ~n~ trò chơi. Trước khi chơi một trò chơi, cần phải học luật chơi của trò chơi đó. Học luật chơi của trò chơi thứ ~i~ mất ~p_i~ phút. Sau khi học luật chơi, có thể chơi trò chơi đó. Chơi trò chơi thứ ~i~ mất ~t_i~ phút. Mỗi trò chơi thứ ~i~ có điểm đánh giá là ~o_i~.

Yêu cầu: Cho tổng cộng tối đa ~d~ phút, hãy chọn cách học và chơi để có điểm đánh giá là lớn nhất. Biết rằng mỗi trò chơi có thể chơi nhiều lần, thời gian học luật chỉ tính một lần.

Input

• Dòng 1: hai số nguyên ~n~ và ~d~ ~(1 \le n, d \le 5000)~;

• Trong ~n~ dòng tiếp theo: mỗi dòng gồm ~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)~.

Output

Ghi ra một số nguyên duy nhất là kết quả cần tìm.

Scoring

Sample Input 1

3 10
2 3 5
5 1 5
3 2 5

Sample Output 1

25

Sample Input 2

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

Sample Output 2

19