GIFTARNG - Gift Arrangement
Duck's birthday is coming soon! Unfortunately, this year nobody will come to Duck's birthday party. To make himself feel better, he has decided to display all birthday gifts received last year, pretending many people celebrate with him this year.
There are N gifts received last year, each in a rectangular gift box with dimensions {Wi (width), Hi (height), Di (depth)}. Gift box is very colorful which makes people happy, so Duck will place all of them in a straight line without changing the order and without any gap between two adjacent boxes, while the total visible area is maximized. To achieve this goal, Duck can rotate each gift box in any direction but the box must stand upright on the ground. That is, it cannot be placed obliquely. Please help him figure out the largest visible area.
Input
The first line is the number of test cases T. (1 ≤ T ≤ 30)
For each test case, it starts with the number of gifts received last year N. (1 ≤ N ≤ 103)
Following N lines, each consisting of three integers Wi (width) Hi (height) Di (depth), representing the dimensions of the i gift box. (1 ≤ Wi, Hi, Di ≤ 105)
Output
Output the largest visible area.
Example
Input: 2 2 100 100 20 3 4 2 3 1 1 1 5 4 3 8 6 8
Output: 26032 330
Explanation
In case 1, one optimal strategy is to rotate the first box to {100, 20, 100} and the second box to {4, 2, 3}.
In case 2, no rotation for the first box and third box, and to rotate the second box to {5, 3, 4}.
hide comments
hello_world123:
2018-07-27 08:12:52
Good implementation problem!! Last edit: 2018-07-27 08:45:57 |
Added by: | him0727 |
Date: | 2018-07-26 |
Time limit: | 0.400s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own problem |