An vừa trở về từ hội chợ trò chơi. Cậu ấ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 chơi của nó. Thời gian để học luật chơi của trò chơi thứ ~i~ là ~p_i~ phút. Sau khi đã học xong luật, có thể chơi trò chơi này. Thời gian chơi trò chơi thứ ~i~ là ~t_i~ phút. Mỗi trò chơi cũng có một điểm số riêng là ~o_i~.

Yêu cầu: Trong những ngày sắp tới, An dự định dành tối đa ~d~ phút để chơi các trò chơi. Cậu ấy muốn tìm ra tổng điểm số tối đa của các trò chơi mà cậu ấy có thể chơi. Mỗi trò chơi có thể được chơi nhiều lần.

Input

• Dòng đầu tiên chứa hai 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 việc chơi trò chơi.

• Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng chứa ba số nguyê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)~, thời gian để học luật chơi, thời gian để chơi và điểm số của trò chơi thứ ~i~.

Output

Ghi dòng duy nhất là tổng điểm số tối đa của các trò chơi mà An có thể chơi.

Scoring

Sample Input 1

3 10
1 1 1
3 2 3
2 3 5

Sample Output 1

11

Notes

Một cách để đạt được tổng điểm là ~11~ như sau: trong phút đầu tiên, An học cách chơi trò chơi đầu tiên, rồi chơi trò này một lần. Sau đó, cậu ấy dành hai phút để học cách chơi trò chơi thứ ba, và trong ~6~ phút còn lại, cậu ấy chơi trò này hai lần. Như vậy, tổng điểm số của các trò chơi là: ~1 + 5 + 5 = 11~.