Given a matrix of integers **A** of size **N x 3** representing the dimensions of **N** rectangular 3-D boxes,

where **A[i][0]** represents the height of the **i ^{th}** box,

You want to create a stack of boxes which is as tall as possible,

but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. You can rotate a box so that any side functions as its base.

It is also allowable to use multiple instances of the same type of box.

Find and return the maximum height of stack achievable.

**Input Format**

```
The only argument given is the integer matrix A.
```

**Output Format**

```
Return the maximum height of stack achievable.
```

**Constraints**

```
1 <= N <= 1000
1 <= A[i][0], A[i][1], A[i][2] <= 10^6
```

**For Example**

```
Input 1:
A = [ [4, 6, 7]
[1, 2, 3]
[4, 5, 6]
[1, 2, 3] ]
Output 1:
60
Explanation 1:
Following are all rotations of the boxes in decreasing order of base area:
10 x 12 x 32
12 x 10 x 32
32 x 10 x 12
4 x 6 x 7
4 x 5 x 6
6 x 4 x 7
5 x 4 x 6
7 x 4 x 6
6 x 4 x 5
1 x 2 x 3
2 x 1 x 3
3 x 1 x 2
The height 60 is obtained by boxes
[ [3, 1, 2], [1, 2, 3], [6, 4, 5], [4, 5, 6], [4, 6, 7], [32, 10, 12], [10, 12, 32] ]
Input 2:
A = [ [4, 5, 6]
[10, 12, 14] ]
Output 2:
34
```

NOTE:You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.

Sign Up

to access hints and editorial solutions for**Box Stacking Problem**

to access hints and editorial solutions for

Loading...