Một trò chơi có luật chơi như sau: Người chơi ban đầu có ~W~ năng lượng và trò chơi có ~N~ màn chơi, màn chơi thứ ~i~ có các thông tin như sau:

• Năng lượng của màn chơi là ~m_i~ - mỗi khi chơi màn này, năng lượng sẽ giảm đi ~m_i~;
• Điểm kinh nghiệm của màn chơi là ~e_i~ - người chơi thu được ~e_i~ điểm kinh nghiệm;
• Trừ điểm kinh nghiệm khi chơi lại là ~s_i~ - mỗi khi chơi lại màn này, số điểm kinh nghiệm nhận được sẽ bị giảm đi ~s_i \times (k - 1)~ (với ~k~ là số lần chơi màn này). Tức là, số điểm kinh nghiệm thu được khi chơi màn chơi thứ ~i~ tại lần thứ ~k~ là ~e_i - s_i \times (k - 1)~;
• Có thể chọn các màn chơi không cần theo thứ tự. Năng lượng của người chơi phải lớn hơn hoặc bằng năng lượng của màn chơi thì mới chơi được màn chơi đó.

Yêu cầu: Đưa ra tổng điểm kinh nghiệm lớn nhất có thể thu được khi chơi trò chơi trên.

Dữ liệu vào từ tệp văn bản GAME.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~N~ và ~W~ ~(N \le 2 \times 10^5;~ ~W \le 3000)~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~m_i, e_i, s_i~ ~(1 \le i \le N; \ m_i \le 3000; \ s_i \le e_i \le 10^5)~.

Kết quả ghi ra tệp văn bản GAME.OUT:

Gồm một số nguyên duy nhất là tổng điểm kinh nghiệm lớn nhất thu được thoả mãn yêu cầu đề bài.

Ví dụ

Input

2 10
2 6 2
5 5 5

Output

15

Giải thích

• Lần ~1~: Chơi màn chơi thứ ~1~: Mất ~2~ năng lượng, điểm kinh nghiệm thu được là ~6~;
• Lần ~2~: Chơi màn chơi thứ ~2~: Mất ~5~ năng lượng, điểm kinh nghiệm thu được là ~5~;
• Lần ~3~: Chơi lại màn chơi thứ ~1~: Mất ~2~ năng lượng, điểm kinh nghiệm thu được là ~4~;

~\Rightarrow~ Vậy mất tổng cộng ~9~ năng lượng và tổng điểm kinh nghiệm thu được là ~15~.

Input

2 8
3 4 2
2 3 1

Output

9

Giải thích

• Lần ~1~: Chơi màn chơi thứ ~1~: Mất ~3~ năng lượng, điểm kinh nghiệm thu được là ~4~;
• Lần ~2~: Chơi lại màn chơi thứ ~1~: Mất ~3~ năng lượng, điểm kinh nghiệm thu được là ~2~;
• Lần ~3~: Chơi màn chơi thứ ~2~: Mất ~2~ năng lượng, điểm kinh nghiệm thu được là ~3~;

~\Rightarrow~ Vậy mất tổng cộng ~8~ năng lượng và tổng điểm kinh nghiệm thu được là ~9~.

Ràng buộc

• Có ~30\%~ số test ứng với ~30\%~ số điểm có ~N \le 2; \ W \le 20~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N, W \le 300~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có ~N \le 1000~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm có năng lượng của màn chơi là như nhau;
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm không có ràng buộc gì thêm.