You have n boxes with different height, width, length. You can either arrange it by their length or width or height. Now you will have to find the volume of a rectangular cuboid box that will contain all the boxes inside it. You will have to determine which way would be more efficient to arrange all the boxes i.e print the minimum volume needed.
"Arrange by height" means, the height of the next box = sum of the height of n boxes.
"Arrange by width" means, the width of the next box = sum of the width of n boxes.
"Arrange by length" means, the length of the next box = sum of the length of n boxes.
Input
The first line will contain T (1 ≤ T ≤ 10) that denotes test cases.
Each test case will contain n (1 ≤ n ≤ 100000) that denotes the number of boxes.
Next n lines will contain 3 integers. The ith line will contain the height, length, width (1 ≤ length, width, height ≤ 10000) of the ith box.
Output
Print the minimum rectangular cuboid needed to arrange all the boxes inside it.
Sample
| Input | Output |
|---|---|
1 4 3 6 9 8 5 4 2 1 8 4 4 4 | 918 |
If you arrange by the height, the final area of the rectangular box will be: 918 (h = 17, l = 6, w = 9) If you arrange by the length, the final area of the rectangular box will be: 1152 (h = 8, l = 16, w = 9) If you arrange by the width, the final area of the rectangular box will be: 1200 (h = 8, l = 6, w = 25)
So it will be efficient to arrange all the boxes by their height. | |
