Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Game of Boxes

By Shahwat_Has9 · 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 \times l \times w. $

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



    Discussion
    Statistics

    90% Solution Ratio

    Jinia_YesminEarliest, 2w ago

    CodefresherFastest, 0.0s

    Jinia_YesminLightest, 131 kB

    mdvirusShortest, 244B

    Submit

    Login to submit