Anna thường chơi bài cùng người bạn Bruno. Sau khi chán các trò chơi dành cho hai người, cô nghĩ ra một trò chơi bài có thể chơi một mình.

Ban đầu có \(N\) lá bài nhiều màu được xếp thành một hàng. Mỗi lá bài có một số nguyên được viết trên đó và có một giá trị. Màu sắc cũng được biểu diễn bằng số nguyên. Lá bài thứ \(i\) tính từ đầu hàng có màu \(C_i\), số \(A_i\) và giá trị \(V_i\).

Ban đầu chồng bài của Anna rỗng. Cô lặp lại thao tác sau:

• Chọn lá bài thứ nhất hoặc thứ ba tính từ đầu hàng. Nếu chồng bài đang không rỗng, cô chỉ được chọn một lá bài có màu hoặc số ghi trên bài trùng với lá trên cùng của chồng bài. Lấy lá đã chọn khỏi hàng và đặt nó lên trên cùng chồng bài.

Trò chơi kết thúc khi không còn lá bài nào có thể chọn. Điểm của Anna là tổng giá trị các lá trong chồng bài khi trò chơi kết thúc.

Yêu cầu

Cho thông tin các lá bài lúc bắt đầu. Hãy tìm số điểm lớn nhất Anna có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(C_i,A_i,V_i\), lần lượt là màu, số ghi trên bài và giá trị của lá bài thứ \(i\).

Dữ liệu ra

In ra một số nguyên là số điểm lớn nhất Anna có thể đạt được.

Ràng buộc

• \(1 \le N \le 500\).
• \(1 \le C_i \le 500\) với mọi \(1 \le i \le N\).
• \(1 \le A_i \le 500\) với mọi \(1 \le i \le N\).
• \(1 \le V_i \le 1\,000\,000\) với mọi \(1 \le i \le N\).

Phân nhóm

• Nhóm 1 (10 điểm): \(N \le 20\)
• Nhóm 2 (15 điểm): \(N \le 50\)
• Nhóm 3 (75 điểm): Không có ràng buộc bổ sung

Ví dụ

5
1 3 2
4 2 9
1 4 6
2 3 3
2 2 1

15

8
11 5 31
2 8 19
2 9 2
11 8 45
4 8 22
4 2 23
6 9 58
6 2 5

160