# 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.

### Statistics

88% Solution Ratio

Jinia_YesminEarliest, 2M ago

Jinia_YesminLightest, 131 kB

mdvirusShortest, 244B

### Related Contests

 Ada Lovelace National Girls' Programming Contest 2020 Ended at 2020-01-02 07:35:00 +0000 UTC Replay of Ada Lovelace National Girls' Programming Contest 2020 Ended at 2020-01-03 17:00:00 +0000 UTC