Hạo đã trở về từ hội chợ trò chơi cờ bàn. Anh ấy mang về nhà \(n\) trò chơi. Trước khi chơi một trò chơi, cần phải học luật của nó. Học luật của trò chơi thứ \(i\) mất \(p_i\) phút. Sau khi học xong luật, 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 cũng có xếp hạng riêng \(o_i\).

Trong những ngày tới, Hạo đã lên kế hoạch dành tối đa \(d\) phút cho các trò chơi cờ bàn. Anh ấy quan tâm đến việc tìm ra tổng xếp hạng tối đa của các trò chơi anh ấy có thể chơi. Mỗi trò chơi có thể được chơi một số lần tùy ý.

Dữ liệu vào

• Dòng đầu tiên chứa các số nguyên \(n\) và \(d\) \((1 \le n, d \le 5000)\), số lượng trò chơi và thời gian dự định dành cho chơi game.
• Dòng thứ \(i\) trong n dòng tiếp theo chứa các số nguyên \(p_i, t_i\) và \(o_i\) \((0 \le pi \le 5000, 1 \le ti \le 5000, 1 \le oi \le 10^9)\), thời gian cần thiết để học luật, thời gian cần thiết để chơi và xếp hạng của trò chơi thứ i.

Dữ liệu ra

• Trong dòng đầu tiên và duy nhất, xuất tổng xếp hạng tối đa của các trò chơi đã chơi.

Chấm điểm

Input 1

3 10
2 3 5
5 1 5
3 2 5

Output 1

25

Input 2

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

Output 2

19

Input 3

3 10
1 1 1
3 2 3
2 3 5

Output 3

11

Giải thích ví dụ thứ ba:

Một cách để đạt tổng điểm \(11\) như sau: trong phút đầu tiên, Hạo học cách chơi trò chơi đầu tiên, sau đó chơi nó một lần. Sau đó, anh ấy dành hai phút để học cách chơi trò chơi thứ ba, và trong 6 phút cuối, anh ấy chơi nó hai lần. Theo cách này, tổng điểm của các trò chơi đã chơi là: \(1 + 5 + 5 = 11\).