밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다.탑은 벽돌을 한 개씩 아래에서 위로 쌓으면서 만들어 간다.

아래의 조건을 만족하면서 가장 높이 탑을 쌓을 수 있는 프로그램을 작성하시오.

1. 벽돌은 회전 시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다.
2. 벽돌들의 높이는 같을 수도 있다.
3. 탑을 쌓을 때 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.
4. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.
5. 같은 넓이 또는 같은 무게인 경우 위에 올릴수 없다

입력 형식

둘 째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인

• 벽돌 밑면의 넓이
• 벽돌의 높이
• 무게

출력 형식

• 첫째 줄에는 탑을 쌓을 때 사용된 벽돌의 수를 출력하고,
• 두 번째 줄부터는 탑의 가장 위 벽돌부터 가장 아래 벽돌까지 차례로 한 줄에 하나씩 벽돌 번호를 빈 칸 없이 출력한다.

입력과 출력의 예

입력

5
25 3 4
4 4 6
9 2 3
16 2 5
1 5 2

출력

3
5
3
1

출처: koi 중등 기출