Khảo cổ Alantis (Bản 1)

Sau một vụ đắm tàu bất ngờ trên đại dương, một đoàn thám hiểm nhỏ bị trôi dạt vào một hòn đảo kỳ lạ, nơi những tàn tích cổ đại lộ ra dưới ánh hoàng hôn. Không ai khác, họ đã vô tình đặt chân lên Atlantis huyền thoại --- thành phố từng được nhắc đến trong thần thoại cổ xưa.

Tuy nhiên, Atlantis không trồi lên vĩnh viễn. Theo những dấu tích cổ còn sót lại, họ nhận ra thành phố này sẽ lại chìm xuống biển sâu trong vòng \(d\) ngày tới. Thời gian không chờ đợi ai, và đoàn thám hiểm phải gấp rút thu thập càng nhiều thông tin, cổ vật và hiểu biết càng tốt trước khi Atlantis biến mất mãi mãi.

Thành phố có \(n\) khu vực khảo cổ. Mỗi khu vực ẩn chứa những cổ vật hoặc kiến thức có giá trị, nhưng việc khai quật và nghiên cứu không hề dễ dàng:

• Để tiếp cận và thu thập những thứ quan trọng ban đầu ở khu vực \(i\), đoàn thám hiểm cần dành ra \(p_i\) ngày.
• Sau khi đã tiếp cận được khu vực này, họ có thể tiếp tục đào sâu nghiên cứu về các hiện vật bên trong. Mỗi lần tìm hiểu thêm tốn \(t_i\) ngày và mang lại \(o_i\) điểm giá trị hữu ích.
• Mỗi khu vực chỉ cần khám phá ban đầu một lần, sau đó có thể tiếp tục khai thác sâu bao nhiêu lần tuỳ ý (miễn là còn đủ thời gian).

Đoàn thám hiểm muốn biết: với tối đa \(d\) ngày trước khi Atlantis lại chìm xuống, họ có thể đạt được tổng giá trị hữu ích lớn nhất là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(d\) \((1 \leq n, d \leq 5000)\) --- số khu vực khảo cổ và số ngày còn lại trước khi Atlantis biến mất.
• Mỗi dòng trong số \(n\) dòng tiếp theo chứa ba số nguyên \(p_i,\ t_i,\ o_i\) \((0 \leq p_i \leq 5000,\ 1 \leq t_i \leq 5000,\ 1 \leq o_i \leq 10^9)\) --- thời gian thu thập ban đầu, thời gian cho mỗi lần nghiên cứu thêm, và giá trị hữu ích tương ứng.

Output

In ra một số nguyên --- giá trị hữu ích lớn nhất mà đoàn thám hiểm có thể đạt được trong \(d\) ngày.

Example

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

19

3 10
1 1 1
3 2 3
2 3 5

11

Scoring

\begintabularc c l
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 50 & \(p_i = 0\) với mọi \(i = 1, 2, \dots, n\)

2 & 50 & Không có ràng buộc bổ sung

\hline
\endtabular