Game of Boxes

Shahwat_Has9 Ada Lovelace National Gir...
Limits 1s, 512 MB

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

InputOutput
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)

Volume=h×l×w. Volume = h \times l \times w.

So it will be efficient to arrange all the boxes by their height.


Submit

Login to submit.

Statistics

88% Solution Ratio
Jinia_YesminEarliest, Jan '20
s_semicolonFastest, 0.0s
Jinia_YesminLightest, 131 kB
mdvirusShortest, 244B
Toph uses cookies. By continuing you agree to our Cookie Policy.