Makacha có viên gạch hình thang cân đánh số từ đến . Viên gạch thứ có đáy nhỏ độ dài , đáy lớn độ dài và chiều cao . Makacha muốn xếp chồng các viên gạch lên nhau để tạo ra một hình tháp. Ngoại trừ viên gạch ở trên cùng, mỗi viên gạch trong tháp phải có đáy nhỏ chứa trọn vẹn đáy lớn của viên gạch duy nhất nằm trên nó (đáy lớn của viên gạch cuối cùng được đặt dưới mặt đất). Chiều cao của tháp là tổng chiều cao của các viên gạch được tạo thành.
Makacha là một người thích sự to lớn, vì vậy anh ta muốn chiều cao của tháp gạch này là lớn nhất có thể. Nhưng vì số lượng viên gạch quá lớn nên anh ta không thể tìm được cách xếp và muốn nhờ bạn giúp. Bạn sẽ giúp Makacha chứ?
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên dương ;
dòng tiếp theo, mỗi dòng chứa ba số nguyên dương .
Dữ liệu ra:
Dòng đầu tiên ghi hai số nguyên là chiều cao lớn nhất có thể của tháp gạch và số lượng viên gạch bạn chọn để xây tháp.
Dòng tiếp theo chứa chỉ số của những viên gạch bạn chọn để xây tháp. Chỉ số các viên gạch được đưa ra theo thứ tự từ trên xuống dưới, có nghĩa là viên gạch được xếp trên cùng được đưa ra đầu tiên... Nếu có nhiều kết quả tối ưu, đưa ra kết quả bất kì.
