Link tải bộ test: https://bit.ly/towerhn

Nhân dịp ngày thành lập Đoàn thanh niên Cộng sản Hồ Chí Minh (26/3/2020), Đoàn trường lên kế hoạch tổ chức một trò chơi như sau: Mỗi đội được phát \(n\) viên gạch hình thang cân đánh số từ 1 tới \(n\). Viên gạch thứ \(i\) có đáy nhỏ độ dài \(a_{i}\), đáy lớn độ dài \(b_{i}\) và chiều cao \(h_{i}\) (\(a_{i} < b_{i}\)). Nhiệm vụ của mỗi đội chơi là phải xếp chồng một số viên gạch lên nhau để tạo ra một hình tháp. Quy tắc xếp tháp như sau:

• Mỗi tầng tháp gồm đúng một viên gạch

• Đáy lớn của viên gạch dưới cùng được đặt trên mặt đất

• Đáy lớn của những viên gạch ở các tầng cao hơn phải nằm trọn vẹn trong đáy nhỏ của viên gạch nằm sát dưới. Nói cách khác, đáy lớn của viên gạch nằm trên phải nhỏ hơn hoặc bằng đáy nhỏ của viên gạch bên dưới.

Chiều cao của tháp là tổng chiều cao các viên gạch tạo thành. Đội nào xếp được tháp cao nhất là đội giành chiến thắng.

Yêu cầu: Giả sử bạn là thành viên của một đội chơi, hãy tìm phương án chọn các viên gạch để xếp được tháp cao nhất có thể.

Dữ liệu vào:

• Dòng 1 chứa số nguyên dương \(n \leq 10^{6}\)

• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên dương \(a_{i},b_{i},h_{i}\) (\(a_{i} < b_{i} \leq 10^{6};h_{i} \leq 10^{6}\))

Kết quả:

• Dòng 1 ghi chiều cao của tháp dựng được

• Dòng 2 ghi số hiệu các viên gạch được dùng để xếp tháp, theo thứ tự từ viên gạch xếp dưới cùng tới viên gạch xếp trên cùng.

Chú ý: 50% số điểm của mỗi test nếu in đúng kết quả dòng 1.

Ví dụ:

Ràng buộc:

+ 40% số điểm ứng với các test có \(n \leq 1000\)

+ 30% số điểm ứng với các test có \(n \leq 10^{5}\)

+ 30% số điểm ứng với các test có \(n \leq 10^{6}.\)