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

• Dòng đầu tiên chứa số nguyên ~ n ~ ~ (1 ≤ n ≤ 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 ≤ t_i ≤ 20, 1 ≤ d_i ≤ 2000, 1 ≤ p_i ≤ 20 ) ~.

Kết quả

• 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.

Ràng buộc

• Có 30% số test có ~ 1≤ n ≤ 10 ~;
• Có 70% số test có ~ 10 < n ≤ 100 ~;

Ví dụ:

Input 1

3
3 7 4
2 6 5
3 7 6 

Output 1

11 

Input 2

2
5 6 1
3 3 5 

Output 2

1