Những con bò muốn đi vào vũ trụ! Chúng muốn đến được quỹ đạo bằng cách xây một kiểu thang máy: một cái tháp khổng lồ làm bằng các khối chồng lên nhau. Chúng có loại khối có thể xây tháp. Mỗi khối loại có chiều cao và có số lượng . Do khả năng bị phá hủy bởi các tia vũ trụ, không có phần nào của khối loại có thể vượt qua độ cao .
Bạn hãy giúp những con bò xây thang máy cao nhất có thể bằng cách chồng các khối lên nhau theo luật trên.
Dữ liệu vào:
Dòng đầu chứa số nguyên dương ;
dòng tiếp theo, dòng thứ chứa ba số nguyên , mỗi số cách nhau một dấu cách.
Dữ liệu ra:
Một số nguyên duy nhất là chiều cao lớn nhất của thang máy.
Ví dụ:
Dữ liệu vào:
3
7 40 3
5 23 8
2 52 6
Dữ liệu ra:
48
Giải thích:
Từ dưới lên: khối loại , khối loại , khối loại (nếu chồng khối loại và loại không hợp lệ vì đỉnh của khối loại vượt quá độ cao ).
