Mấy hôm nay trời mưa nhiều, lượng nước dâng lên khá nhanh. Ngôi nhà Bờm đang sống ở vùng thấp trũng nên khó tránh khỏi ngập lụt. Bờm là người đam mê công nghệ nên trong nhà của cậu ta có rất nhiều món đồ công nghệ có giá trị nhưng lại dễ hỏng nếu bị ngập nước. Để bảo vệ những món đồ công nghệ này khi nước dâng cao, Bờm phải mang chúng đến nơi an toàn. Cậu ta phải đi lên đi xuống nhiều lần vì mỗi lần chỉ mang theo một món đồ. Món đồ thứ \(i\) có giá trị là \(p_{i}\) (đồng), cần \(t_{i}\) phút để di chuyển xong món đồ thứ \(i\), bắt đầu từ phút thứ \(d_{i}\) món đồ thứ \(i\) sẽ bị ngập.

Yêu cầu: Hãy cho biết tổng giá trị lớn nhất của những món đồ mà Bờm có thể mang đi.

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

• Dòng đầu tiên chứa số nguyên \(n\ (1 \leq n \leq 100)\) là số lượng món đồ công nghệ;

• \(n\) dòng tiếp theo mỗi dòng chứa ba số nguyên được ghi cách nhau bởi dấu cách lần lượt là \(t_{i},\ d_{i},\ p_{i}\ (1 \leq t_{i} \leq 20,\ 1 \leq d_{i} \leq 2000,\ 1 \leq p_{i} \leq 20)\ \).

Kết quả: Đưa ra tệp văn bản LULUT.OUT một số nguyên duy nhất là tổng giá trị lớn nhất của các món đồ có thể mang đi.

Ví dụ:

Giải thích:

Ví dụ 1: Bờm di chuyển được 2 món đồ, đầu tiên Bờm di chuyển xong món đồ số 2 mất 2 phút, sau đó di chuyển xong món đồ số 3 mất 5 (= 2+3) phút. Không thể lấy thêm món đồ số 1 vì sẽ mất 8 (=5+3) phút (8>7). Tổng giá trị là 5 + 6 = 11.

Ví dụ 2: Bờm không thể di chuyển món đồ thứ 2 vì chưa di chuyển xong thì nước đã ngập (thời gian di chuyển mất 3 phút mà lúc đó nước đã ngập đến) nên Bờm chỉ có thể di chuyển món đồ số 1.

Ràng buộc:

+ Có 30% số test tương ứng với 30% số điểm có \(1 \leq n \leq 10\);

+ Có 70% số test còn lại tương ứng với 70% số điểm có \(10 < n \leq 100\);