You are given a set of N types of rectangular 3-D boxes, where the ith box has height h, width w and length l. Your task is 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. Of course, 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. Your task is to complete the function maxHeight which returns the height of the highest possible stack so formed.
 
Note: 
Base of the lower box should be strictly larger than that of the new box we're going to place. This is in terms of both length and width, not just in terms of area. So, two boxes with same base cannot be placed one over the other.
 
Example 1:
Input:
n = 4
height[] = {4,1,4,10}
width[] = {6,2,5,12}
length[] = {7,3,6,32}
Output: 60
Explanation: One way of placing the boxes is
as follows in the bottom to top manner:
(Denoting the boxes in (l, w, h) manner)
(12, 32, 10) (10, 12, 32) (6, 7, 4) 
(5, 6, 4) (4, 5, 6) (2, 3, 1) (1, 2, 3)
Hence, the total height of this stack is
10 + 32 + 4 + 4 + 6 + 1 + 3 = 60.
No other combination of boxes produces a
height greater than this.
Example 2:
Input:
n = 3
height[] = {1,4,3}
width[] = {2,5,4}
length[] = {3,6,1}
Output: 15
Explanation: One way of placing the boxes is
as follows in the bottom to top manner:
(Denoting the boxes in (l, w, h) manner)
(5, 6, 4) (4, 5, 6) (3, 4, 1), (2, 3, 1) 
(1, 2, 3).
Hence, the total height of this stack is
4 + 6 + 1 + 1 + 3 = 15
No other combination of boxes produces a
height greater than this.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxHeight() which takes three arrays height[], width[], length[], and N as a number of boxes and returns the highest possible stack height which could be formed.
Expected Time Complexity : O(N*N)
Expected Auxiliary Space: O(N)
Constraints:
1<= N <=100
1<= l,w,h <=100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

    def maxHeight(self,height, width, length, n):

        #Code here

Solutions:
class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = [[] for i in range(3 * n)]
		index = 0
		for i in range(n):
			boxes[index].append(height[i])
			boxes[index].append(min(width[i], length[i]))
			boxes[index].append(max(width[i], length[i]))
			index += 1
			boxes[index].append(width[i])
			boxes[index].append(min(height[i], length[i]))
			boxes[index].append(max(height[i], length[i]))
			index += 1
			boxes[index].append(length[i])
			boxes[index].append(min(width[i], height[i]))
			boxes[index].append(max(width[i], height[i]))
			index += 1
		boxes.sort(reverse=True, key=lambda x: x[2] * x[1])
		n *= 3
		msh = [0] * n
		for i in range(n):
			msh[i] = boxes[i][0]
			for j in range(i):
				if boxes[i][1] < boxes[j][1] and boxes[i][2] < boxes[j][2]:
					if msh[i] < msh[j] + boxes[i][0]:
						msh[i] = msh[j] + boxes[i][0]
		return max(msh)


class Box:

	def __init__(self, length, width, height):
		self.length = length
		self.width = width
		self.height = height

	def __lt__(self, other):
		return self.length * self.width < other.length * other.width

class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = []
		for i in range(n):
			boxes.append(Box(max(length[i], width[i]), min(length[i], width[i]), height[i]))
			boxes.append(Box(max(length[i], height[i]), min(length[i], height[i]), width[i]))
			boxes.append(Box(max(width[i], height[i]), min(width[i], height[i]), length[i]))
		boxes.sort(reverse=True)
		dp = [box.height for box in boxes]
		res = max(dp)
		for i in range(1, 3 * n):
			for j in range(0, i):
				if boxes[i].length < boxes[j].length and boxes[i].width < boxes[j].width:
					if dp[i] < dp[j] + boxes[i].height:
						dp[i] = dp[j] + boxes[i].height
						res = max(res, dp[i])
		return res


import functools

class Solution:

	def maxHeight(self, height, width, length, n):

		def mycmp(a, b):
			if a[1] * a[2] > b[1] * b[2]:
				return 1
			else:
				return -1
		boxes = [[0, 0, 0] for i in range(3 * n)]
		j = 0
		for i in range(n):
			boxes[j][0] = height[i]
			boxes[j][1] = max(width[i], length[i])
			boxes[j][2] = min(width[i], length[i])
			j += 1
			boxes[j][0] = width[i]
			boxes[j][1] = max(height[i], length[i])
			boxes[j][2] = min(height[i], length[i])
			j += 1
			boxes[j][0] = length[i]
			boxes[j][1] = max(width[i], height[i])
			boxes[j][2] = min(width[i], height[i])
			j += 1
		boxes = sorted(boxes, key=functools.cmp_to_key(mycmp))
		dp = [boxes[i][0] for i in range(3 * n)]
		ans = dp[0]
		for i in range(1, 3 * n):
			m = dp[i]
			for j in range(i):
				if boxes[i][1] > boxes[j][1] and boxes[i][2] > boxes[j][2]:
					dp[i] = max(dp[i], m + dp[j])
			ans = max(dp[i], ans)
		return ans


class Box:

	def __init__(self, l, w, h):
		self.l = l
		self.w = w
		self.h = h

	def __lt__(self, other):
		return self.l * self.w < other.l * other.w

	def __repr__(self):
		return str(self.l) + ' ' + str(self.w) + ' ' + str(self.h)

class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = [Box(0, 0, 0) for i in range(n * 3)]
		index = 0
		for i in range(n):
			boxes[index].l = max(length[i], width[i])
			boxes[index].w = min(length[i], width[i])
			boxes[index].h = height[i]
			index += 1
			boxes[index].l = max(width[i], height[i])
			boxes[index].w = min(width[i], height[i])
			boxes[index].h = length[i]
			index += 1
			boxes[index].l = max(height[i], length[i])
			boxes[index].w = min(height[i], length[i])
			boxes[index].h = width[i]
			index += 1
		boxes.sort(reverse=True)
		n = n * 3
		msh = [0] * n
		for i in range(n):
			msh[i] = boxes[i].h
		for i in range(1, n):
			for j in range(0, i):
				if boxes[i].l < boxes[j].l and boxes[i].w < boxes[j].w:
					if msh[i] < msh[j] + boxes[i].h:
						msh[i] = msh[j] + boxes[i].h
		return max(msh)


class Solution:

	def fits(self, base1, base2):
		(h1, l1, w1) = base1
		(h2, l2, w2) = base2
		if w2 < w1 and l2 < l1:
			return True
		elif w2 < l1 and l2 < w1:
			return True
		else:
			return False

	def maxHeight(self, height, width, length, n):
		boxes = []
		for i in range(n):
			boxes.append([height[i], width[i], length[i]])
			boxes.append([width[i], height[i], length[i]])
			boxes.append([length[i], width[i], height[i]])
		areaSorted = sorted(boxes, key=lambda x: x[1] * x[2], reverse=True)
		dp = [-float('inf') for _ in range(3 * n)]
		dp[0] = areaSorted[0][0]
		for i in range(1, 3 * n):
			height = areaSorted[i][0]
			base1 = areaSorted[i]
			maxHeight = height
			for j in range(i):
				base2 = areaSorted[j]
				if self.fits(base2, base1):
					maxHeight = max(maxHeight, dp[j] + height)
			dp[i] = maxHeight
		return max(dp)


class Solution:

	def maxHeight(self, height, width, length, n):
		temp = []
		for i in range(n):
			(l, w, h) = (length[i], width[i], height[i])
			temp.append([l * w, min(l, w), max(l, w), h])
			temp.append([l * h, min(l, h), max(l, h), w])
			temp.append([w * h, min(w, h), max(w, h), l])
		temp.sort()
		(lis, ans) = ([i[3] for i in temp], 0)
		for i in range(3 * n):
			(area_i, length_i, width_i, height_i) = temp[i]
			for j in range(i):
				(area_j, length_j, width_j, height_j) = temp[j]
				if length_j < length_i and width_j < width_i:
					if lis[i] < lis[j] + height_i:
						lis[i] = lis[j] + height_i
			ans = max(ans, lis[i])
		return ans


class Solution:

	def maxHeight(self, height, width, length, n):
		(h, w, l) = (height, width, length)
		height = h + w + l
		width = w + l + h
		length = l + h + w
		n = n * 3

		def make_boxes(h, w, l):
			boxes = []
			for i in range(len(h)):
				d = (max(h[i], w[i]), min(h[i], w[i]), l[i])
				boxes.append(d)
			return boxes
		boxes = make_boxes(height, width, length)
		boxes = sorted(boxes, key=lambda x: x[0] * x[1], reverse=True)

		def comp_base(a, b):
			if a[0] > b[0] and a[1] > b[1]:
				return True
			return False
		ans = [x[2] for x in boxes]
		for i in range(1, len(boxes)):
			box1 = boxes[i]
			for j in range(i):
				box2 = boxes[j]
				if comp_base(box2, box1):
					ans[i] = max(ans[i], ans[j] + box1[2])
		return max(ans)


class Solution:

	def fit(self, bottomBase, topBase):
		(l1, w1) = bottomBase
		(lt, wt) = topBase
		if lt < l1 and wt < w1:
			return True
		if wt < l1 and lt < w1:
			return True
		return False

	def maxHeight(self, height, width, length, n):
		A = []
		for i in range(len(height)):
			A.append([height[i], width[i], length[i]])
			A.append([width[i], length[i], height[i]])
			A.append([length[i], height[i], width[i]])
		dp = [0 for _ in range(len(A))]
		sortedA = sorted(A, key=lambda x: x[1] * x[2])
		dp[0] = sortedA[0][0]
		for i in range(1, len(sortedA)):
			(hbase, lbase, wbase) = sortedA[i]
			maximum = hbase
			for j in range(i):
				(h2, l2, w2) = sortedA[j]
				if self.fit([lbase, wbase], [l2, w2]):
					maximum = max(maximum, hbase + dp[j])
			dp[i] = maximum
		return max(dp)


class Solution:

	def maxHeight(self, height, width, length, n):
		t = [-1 for i in range(3 * n)]
		boxes = []
		for i in range(n):
			for j in range(3):
				dim1 = length[i]
				dim2 = width[i]
				dim3 = height[i]
				if j == 1:
					(dim1, dim2, dim3) = (dim2, dim3, dim1)
				elif j == 2:
					(dim1, dim2, dim3) = (dim3, dim1, dim2)
				boxes.append([dim1 * dim2, dim1, dim2, dim3])
		boxes.sort()
		for i in range(3 * n):
			t[i] = boxes[i][3]
		gmax = 0
		for i in range(3 * n):
			for j in range(i):
				if boxes[i][1] > boxes[j][1] and boxes[i][2] > boxes[j][2] or (boxes[i][1] > boxes[j][2] and boxes[i][2] > boxes[j][1]):
					t[i] = max(t[i], t[j] + boxes[i][3])
			gmax = max(t[i], gmax)
		return gmax


class Solution:

	def maxHeight(self, h, b, l, n):

		def compare(val):
			return val[1] * val[2]

		def LIS(dim, n):
			lis = []
			for i in range(n):
				lis.append(dim[i][0])
			ans = lis[0]
			for i in range(1, n):
				maxi = 0
				for j in range(0, i):
					if dim[j][1] > dim[i][1] and dim[j][2] > dim[i][2]:
						maxi = max(maxi, lis[j])
				lis[i] += maxi
				ans = max(ans, lis[i])
			return ans
		dim = []
		for i in range(n):
			arr = [h[i], b[i], l[i]]
			arr.sort()
			dim.append([arr[0], arr[1], arr[2]])
			dim.append([arr[1], arr[0], arr[2]])
			dim.append([arr[2], arr[0], arr[1]])
		dim.sort(key=compare, reverse=True)
		ans = LIS(dim, len(dim))
		return ans


class Solution:

	def stackHelper(self, i):
		if self.M[i] != -1:
			return self.M[i]
		cur_box = self.boxes[i]
		max_height = 0
		for (j, box) in enumerate(self.boxes):
			if box[0] < cur_box[0] and box[1] < cur_box[1]:
				height = self.stackHelper(j)
				max_height = max(max_height, height)
		self.M[i] = max_height + cur_box[2]
		return self.M[i]

	def maxHeight(self, height, width, length, n):
		self.M = [-1 for i in range(6 * n)]
		self.boxes = []
		for i in range(n):
			(h, w, l) = (height[i], width[i], length[i])
			variations = [(l, w, h), (w, l, h), (h, l, w), (l, h, w), (h, w, l), (w, h, l)]
			self.boxes += variations
		for (i, box) in enumerate(self.boxes):
			self.stackHelper(i)
		return max(self.M)


class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = []
		for i in range(n):
			box1 = [height[i], max(width[i], length[i]), min(width[i], length[i])]
			box2 = [width[i], max(height[i], length[i]), min(height[i], length[i])]
			box3 = [length[i], max(height[i], width[i]), min(height[i], width[i])]
			boxes.append(box1)
			boxes.append(box2)
			boxes.append(box3)
		boxes.sort(key=lambda x: -1 * x[1] * x[2])
		dp = [0] * len(boxes)
		for i in range(len(boxes)):
			dp[i] = boxes[i][0]
			for j in range(i):
				if boxes[j][1] > boxes[i][1] and boxes[j][2] > boxes[i][2]:
					dp[i] = max(dp[i], dp[j] + boxes[i][0])
		return max(dp)


class Solution:

	def maxHeight(self, h, w, l, n):
		A = [[h[i], w[i], l[i]] for i in range(n)]
		boxes = []
		for [ln, bd, wd] in A:
			boxes.append((ln, max(wd, bd), min(bd, wd)))
			boxes.append((bd, max(wd, ln), min(ln, wd)))
			boxes.append((wd, max(ln, bd), min(bd, ln)))
		boxes.sort(key=lambda x: -1 * x[1] * x[2])
		n = len(boxes)
		dp = [0] * n
		ans = 0
		for i in range(n):
			dp[i] = boxes[i][0]
			for j in range(i):
				if boxes[j][2] > boxes[i][2] and boxes[j][1] > boxes[i][1]:
					dp[i] = max(dp[i], dp[j] + boxes[i][0])
			ans = max(ans, dp[i])
		return ans


class Solution:

	def maxHeight(self, height, width, length, n):
		arr = []
		for i in range(n):
			arr.append((min(length[i], width[i]), max(length[i], width[i]), height[i]))
			arr.append((min(width[i], height[i]), max(width[i], height[i]), length[i]))
			arr.append((min(height[i], length[i]), max(height[i], length[i]), width[i]))
		arr.sort(key=lambda x: x[0] * x[1], reverse=True)
		dp = [0] * (3 * n)
		m = 0
		for i in range(3 * n):
			dp[i] = arr[i][2]
			for j in range(i):
				if arr[j][0] > arr[i][0] and arr[j][1] > arr[i][1]:
					dp[i] = max(dp[i], dp[j] + arr[i][2])
			m = max(m, dp[i])
		return m


class Solution:

	def maxHeight(self, height, width, length, n):
		arr = []
		for i in range(n):
			arr.append([length[i], width[i], height[i]])
			arr.append([length[i], height[i], width[i]])
			arr.append([width[i], height[i], length[i]])
		arr.sort(key=lambda x: x[0] * x[1])
		dp = [arr[i][2] for i in range(len(arr))]
		for i in range(1, len(arr)):
			for j in range(i):
				if arr[i][0] > arr[j][0] and arr[i][1] > arr[j][1] or (arr[i][0] > arr[j][1] and arr[i][1] > arr[j][0]):
					if dp[j] + arr[i][2] > dp[i]:
						dp[i] = dp[j] + arr[i][2]
		return max(dp)


class Solution:

	def maxHeight(self, height, width, length, N):
		alltuples = []
		for n in range(N):
			alltuples.append((height[n - 1], width[n - 1], length[n - 1]))
			alltuples.append((width[n - 1], length[n - 1], height[n - 1]))
			alltuples.append((length[n - 1], height[n - 1], width[n - 1]))
		alltuples.sort(key=lambda x: x[0] * x[1])
		heights = [h for (l, w, h) in alltuples]
		i = 0
		M = 0
		for (l1, w1, h1) in alltuples:
			towers = []
			n = 0
			for (l2, w2, h2) in alltuples:
				H = heights[n]
				if l1 > l2 and w1 > w2 or (l1 > w2 and w1 > l2):
					towers.append(h1 + H)
				n += 1
			if len(towers) > 0:
				heights[i] = max(towers)
			i += 1
		return max(heights)


class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = []
		for i in range(n):
			a = [height[i], max(width[i], length[i]), min(width[i], length[i])]
			boxes.append(a)
			a = [width[i], max(height[i], length[i]), min(height[i], length[i])]
			boxes.append(a)
			a = [length[i], max(height[i], width[i]), min(height[i], width[i])]
			boxes.append(a)
		boxes.sort(key=lambda x: x[1] * x[2])
		ans = 0
		dp = [i[0] for i in boxes]
		for i in range(1, n * 3):
			for j in range(i):
				if boxes[i][1] > boxes[j][1] and boxes[i][2] > boxes[j][2]:
					dp[i] = max(dp[i], dp[j] + boxes[i][0])
				ans = max(ans, dp[i])
		return ans


from functools import lru_cache

class Solution:

	def maxHeight(self, height, width, length, n):

		@lru_cache(None)
		def fun(x, y):
			nonlocal n
			ans = float('-inf')
			for i in range(n):
				if height[i] < x and width[i] < y:
					ans = max(ans, fun(height[i], width[i]) + length[i])
				if height[i] < x and length[i] < y:
					ans = max(ans, fun(height[i], length[i]) + width[i])
				if length[i] < x and width[i] < y:
					ans = max(ans, fun(length[i], width[i]) + height[i])
				if length[i] < x and height[i] < y:
					ans = max(ans, fun(length[i], height[i]) + width[i])
				if width[i] < x and length[i] < y:
					ans = max(ans, fun(width[i], length[i]) + height[i])
				if width[i] < x and height[i] < y:
					ans = max(ans, fun(width[i], height[i]) + length[i])
			return ans if ans != float('-inf') else 0
		return fun(101, 101)


class Solution:

	def maxHeight(self, height, width, length, n):
		arr = []
		for i in range(n):
			x = height[i]
			y = max(length[i], width[i])
			z = min(length[i], width[i])
			arr.append([y, z, x])
			x = length[i]
			y = max(width[i], height[i])
			z = min(width[i], height[i])
			arr.append([y, z, x])
			x = width[i]
			y = max(length[i], height[i])
			z = min(length[i], height[i])
			arr.append([y, z, x])
		(l, w) = (float('inf'), float('inf'))
		mp = {}
		res = self.maxHeightHelper(arr, l, w, mp)
		return res

	def maxHeightHelper(self, arr, l, w, mp):
		res = 0
		if (l, w) in mp:
			return mp[l, w]
		for i in range(len(arr)):
			if l > arr[i][0] and w > arr[i][1]:
				res = max(res, arr[i][2] + self.maxHeightHelper(arr, arr[i][0], arr[i][1], mp))
		mp[l, w] = res
		return res


class Solution:

	def maxHeight(self, height, width, length, n):
		arr = set()
		for i in range(n):
			arr.add((height[i], width[i], length[i]))
			arr.add((width[i], height[i], length[i]))
			arr.add((length[i], width[i], height[i]))
			arr.add((width[i], length[i], height[i]))
			arr.add((length[i], height[i], width[i]))
			arr.add((height[i], length[i], width[i]))
		arr = sorted(list(arr))
		dp = [x[2] for x in arr]
		for i in range(1, len(arr)):
			for j in range(i):
				if arr[j][0] < arr[i][0] and arr[j][1] < arr[i][1]:
					dp[i] = max(dp[i], arr[i][2] + dp[j])
		return max(dp)


import math

class Solution:

	def high(self, arr, n, memo, l=math.inf, w=math.inf):
		key = (l, w)
		if key in memo:
			return memo[key]
		res = 0
		for i in range(n):
			if arr[i][0] < l and arr[i][1] < w:
				res = max(res, arr[i][2] + self.high(arr, n, memo, arr[i][0], arr[i][1]))
			elif arr[i][0] < w and arr[i][1] < l:
				res = max(res, arr[i][2] + self.high(arr, n, memo, arr[i][1], arr[i][0]))
		memo[key] = res
		return memo[key]

	def maxHeight(self, height, width, length, n):
		arr = []
		for i in range(n):
			arr.append((length[i], width[i], height[i]))
			arr.append((width[i], height[i], length[i]))
			arr.append((height[i], length[i], width[i]))
		memo = {}
		return self.high(arr, n * 3, memo)


class Solution:

	def maxHeight(self, h, w, l, n):
		a = []
		for i in range(n):
			a.append((h[i], min(w[i], l[i]), max(w[i], l[i])))
			a.append((w[i], min(h[i], l[i]), max(h[i], l[i])))
			a.append((l[i], min(w[i], h[i]), max(w[i], h[i])))
		a.sort(key=lambda x: x[1] * x[2])
		n *= 3
		x = [p[0] for p in a]
		j = 1
		while j < n:
			i = 0
			while i < j:
				if a[j][1] > a[i][1] and a[j][2] > a[i][2]:
					x[j] = max(x[j], x[i] + a[j][0])
				i += 1
			j += 1
		return max(x)


class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = []
		for i in range(n):
			h = height[i]
			l = max(length[i], width[i])
			w = min(length[i], width[i])
			boxes.append([l, w, h])
			h = length[i]
			l = max(height[i], width[i])
			w = min(height[i], width[i])
			boxes.append([l, w, h])
			h = width[i]
			l = max(length[i], height[i])
			w = min(length[i], height[i])
			boxes.append([l, w, h])
		boxes.sort(key=lambda x: x[0] * x[1], reverse=True)
		dp = [box[2] for box in boxes]
		maxi = dp[0]
		for i in range(1, len(boxes)):
			for j in range(i):
				if boxes[i][0] < boxes[j][0] and boxes[i][1] < boxes[j][1]:
					dp[i] = max(dp[i], dp[j] + boxes[i][2])
				maxi = max(maxi, dp[i])
		return maxi


class Solution:

	def maxHeight(self, h, w, l, n):
		a = []
		for i in range(n):
			x = h[i]
			y = max(l[i], w[i])
			z = min(l[i], w[i])
			a.append([y, z, x])
			x = l[i]
			y = max(h[i], w[i])
			z = min(h[i], w[i])
			a.append([y, z, x])
			x = w[i]
			y = max(l[i], h[i])
			z = min(l[i], h[i])
			a.append([y, z, x])
		n *= 3
		a.sort(key=lambda x: x[0] * x[1], reverse=True)
		dp = [i[2] for i in a]
		for i in range(1, n):
			for j in range(i):
				if a[j][0] > a[i][0] and a[j][1] > a[i][1]:
					dp[i] = max(dp[i], dp[j] + a[i][2])
		return max(dp)


class Solution:

	def maxHeight(self, height, width, length, n):
		dataset = list()
		for (h, w, l) in zip(height, width, length):
			newdata = [[h, w, l], [h, l, w], [w, h, l], [w, l, h], [l, h, w], [l, w, h]]
			dataset.extend(newdata)
		dataset.sort()
		hold = self.solve(dataset, len(dataset))
		return hold

	def solve(self, array, n):
		currRow = [0 for j in range(n + 1)]
		nextRow = [0 for j in range(n + 1)]
		for curr in range(n - 1, -1, -1):
			for prev in range(n - 1, -2, -1):
				take = 0
				if prev == -1 or self.check(array[curr], array[prev]):
					take = array[curr][2] + nextRow[curr + 1]
				nottake = 0 + nextRow[prev + 1]
				currRow[prev + 1] = max(take, nottake)
			nextRow = currRow.copy()
		return nextRow[0]

	def check(self, base, newbox):
		if newbox[0] < base[0] and newbox[1] < base[1]:
			return True
		return False


class Solution:

	def fitBox(self, bbox, tbox):
		return bbox[1] > tbox[1] and bbox[2] > tbox[2]

	def maxHeight(self, height, width, length, n):
		boxes = [[] for _ in range(n * 3)]
		k = 0
		for i in range(n):
			boxes[k].append(height[i])
			boxes[k] += sorted([length[i], width[i]], reverse=True)
			k += 1
			boxes[k].append(length[i])
			boxes[k] += sorted([height[i], width[i]], reverse=True)
			k += 1
			boxes[k].append(width[i])
			boxes[k] += sorted([height[i], length[i]], reverse=True)
			k += 1
		boxes.sort(key=lambda x: x[1], reverse=True)
		d = [boxes[i][0] for i in range(n * 3)]
		for i in range(1, n * 3):
			for j in range(i):
				if self.fitBox(boxes[j], boxes[i]):
					d[i] = max(d[i], d[j] + boxes[i][0])
		return max(d)


import math

class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = [(height[i], width[i], length[i]) for i in range(n)]
		dp = [[-1 for i in range(102)] for j in range(102)]
		return self.helper(boxes, 101, 101, dp)

	def helper(self, boxes, prev_w, prev_len, dp):
		if dp[prev_w][prev_len] != -1:
			return dp[prev_w][prev_len]
		dp[prev_w][prev_len] = 0
		for box in boxes:
			(a, b, c) = box
			if b < prev_w and c < prev_len:
				dp[prev_w][prev_len] = max(dp[prev_w][prev_len], self.helper(boxes, b, c, dp) + a)
			if c < prev_w and b < prev_len:
				dp[prev_w][prev_len] = max(dp[prev_w][prev_len], self.helper(boxes, c, b, dp) + a)
			if a < prev_w and c < prev_len:
				dp[prev_w][prev_len] = max(dp[prev_w][prev_len], self.helper(boxes, a, c, dp) + b)
			if c < prev_w and a < prev_len:
				dp[prev_w][prev_len] = max(dp[prev_w][prev_len], self.helper(boxes, c, a, dp) + b)
			if a < prev_w and b < prev_len:
				dp[prev_w][prev_len] = max(dp[prev_w][prev_len], self.helper(boxes, a, b, dp) + c)
			if b < prev_w and a < prev_len:
				dp[prev_w][prev_len] = max(dp[prev_w][prev_len], self.helper(boxes, b, a, dp) + c)
		return dp[prev_w][prev_len]


class Solution:

	def maxHeight(self, height, width, length, n):

		def solve(curl, curw, d={}):
			if (curl, curw) in d:
				return d[curl, curw]
			res = 0
			for i in range(n):
				if length[i] > curl and width[i] > curw:
					res = max(res, height[i] + solve(length[i], width[i], d))
				if length[i] > curl and height[i] > curw:
					res = max(res, width[i] + solve(length[i], height[i], d))
				if height[i] > curl and width[i] > curw:
					res = max(res, length[i] + solve(height[i], width[i], d))
				if height[i] > curl and length[i] > curw:
					res = max(res, width[i] + solve(height[i], length[i], d))
				if width[i] > curl and length[i] > curw:
					res = max(res, height[i] + solve(width[i], length[i], d))
				if width[i] > curl and height[i] > curw:
					res = max(res, length[i] + solve(width[i], height[i], d))
			d[curl, curw] = res
			return d[curl, curw]
		return solve(0, 0)


class Box:

	def __init__(self, l, w, h):
		self.l = l
		self.w = w
		self.h = h

	def __lt__(self, other):
		return self.l * self.w < other.l * other.w

	def __repr__(self):
		return '({0}, {1}, {2})'.format(self.l, self.w, self.h)

class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = []
		for i in range(n):
			boxes.append(Box(length[i], width[i], height[i]))
		rots = [Box(0, 0, 0) for _ in range(3 * n)]
		index = 0
		for i in range(n):
			rots[index].h = boxes[i].h
			rots[index].l = max(boxes[i].l, boxes[i].w)
			rots[index].w = min(boxes[i].l, boxes[i].w)
			index += 1
			rots[index].h = boxes[i].l
			rots[index].l = max(boxes[i].w, boxes[i].h)
			rots[index].w = min(boxes[i].w, boxes[i].h)
			index += 1
			rots[index].h = boxes[i].w
			rots[index].l = max(boxes[i].l, boxes[i].h)
			rots[index].w = min(boxes[i].l, boxes[i].h)
			index += 1
		n = 3 * n
		rots.sort(reverse=True)
		msh = [0] * n
		for i in range(n):
			msh[i] = rots[i].h
		for i in range(1, n):
			for j in range(i):
				if rots[i].l < rots[j].l and rots[i].w < rots[j].w and (msh[j] + rots[i].h > msh[i]):
					msh[i] = msh[j] + rots[i].h
		max_height = 0
		for i in range(n):
			max_height = max(max_height, msh[i])
		return max_height


from collections import defaultdict

class Solution:

	def maxHeight(self, height, width, length, n):
		areas = defaultdict(int)
		for (l, w, h) in zip(length, width, height):
			areas[tuple(sorted([l, w]))] = max(areas[tuple(sorted([l, w]))], h)
			areas[tuple(sorted([w, h]))] = max(areas[tuple(sorted([w, h]))], l)
			areas[tuple(sorted([h, l]))] = max(areas[tuple(sorted([h, l]))], w)
		self.numbers = sorted(areas.items(), key=lambda x: x[0][0] * x[0][1])
		self.dp = {}
		return self.getMaxLength()

	def getMaxLength(self, i=0, last=(-1, -1)):
		if i == len(self.numbers):
			return 0
		if (i, last) in self.dp:
			return self.dp[i, last]
		a = -1
		if last[0] < self.numbers[i][0][0] and last[1] < self.numbers[i][0][1]:
			a = self.getMaxLength(i + 1, self.numbers[i][0]) + self.numbers[i][1]
		b = self.getMaxLength(i + 1, last)
		self.dp[i, last] = max(a, b)
		return self.dp[i, last]


class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = []
		for i in range(n):
			boxes.append([width[i], length[i], height[i]])
			boxes.append([length[i], width[i], height[i]])
			boxes.append([width[i], height[i], length[i]])
			boxes.append([height[i], width[i], length[i]])
			boxes.append([length[i], height[i], width[i]])
			boxes.append([height[i], length[i], width[i]])
		boxes.sort()
		lis = []
		for i in range(6 * n):
			lis.append(boxes[i][2])
		for i in range(1, 6 * n):
			for j in range(i):
				if boxes[j][0] < boxes[i][0] and boxes[j][1] < boxes[i][1] and (boxes[j][0] * boxes[j][1] < boxes[i][0] * boxes[i][1]):
					lis[i] = max(lis[i], boxes[i][2] + lis[j])
		return max(lis)


class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = []
		for i in range(n):
			boxes.append([height[i], width[i], length[i]])
			boxes.append([width[i], length[i], height[i]])
			boxes.append([length[i], height[i], width[i]])
			boxes.append([height[i], length[i], width[i]])
			boxes.append([length[i], width[i], height[i]])
			boxes.append([width[i], height[i], length[i]])
		n = 6 * n
		boxes.sort(reverse=True, key=lambda x: x[0] * x[1])
		dp = [None for i in range(n)]
		dp[n - 1] = boxes[n - 1][2]
		ans = 0
		for i in range(n):
			ans = max(self.find(boxes, i, dp, n), ans)
		return ans

	def find(self, boxes, i, dp, n):
		if dp[i]:
			return dp[i]
		ans = boxes[i][2]
		for j in range(i + 1, n):
			if boxes[i][0] > boxes[j][0] and boxes[i][1] > boxes[j][1]:
				ans = max(self.find(boxes, j, dp, n) + boxes[i][2], ans)
		dp[i] = ans
		return ans


class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = []
		for i in range(n):
			boxes.append([height[i], width[i], length[i]])
			boxes.append([length[i], width[i], height[i]])
			boxes.append([height[i], length[i], width[i]])
			boxes.append([width[i], height[i], length[i]])
			boxes.append([width[i], length[i], height[i]])
			boxes.append([length[i], height[i], width[i]])
		boxes.sort()
		dp = [0 for i in range(len(boxes))]
		max_h = dp[0]
		for i in range(len(boxes)):
			h = boxes[i][2]
			dp[i] = boxes[i][2]
			res = 0
			for j in range(i):
				if boxes[j][0] < boxes[i][0] and boxes[j][1] < boxes[i][1]:
					dp[i] = max(dp[i], h + dp[j])
			max_h = max(max_h, dp[i])
		return max_h


class Solution:

	def maxHeight(self, height, width, length, n):
		box = set()
		for i in range(n):
			h = height[i]
			l = max(length[i], width[i])
			w = min(length[i], width[i])
			box.add((l, w, h))
			h = length[i]
			l = max(width[i], height[i])
			w = min(width[i], height[i])
			box.add((l, w, h))
			h = width[i]
			l = max(length[i], height[i])
			w = min(length[i], height[i])
			box.add((l, w, h))
		box = list(box)
		box.sort(key=lambda x: x[0] * x[1], reverse=True)
		dp_max_heights = [ele[2] for ele in box]
		dp_indexes = [0 for _ in range(len(box))]
		maxi = dp_max_heights[0]
		n = len(box)
		for i in range(1, n):
			for j in range(i):
				if box[i][0] < box[j][0] and box[i][1] < box[j][1]:
					original = dp_max_heights[i]
					dp_max_heights[i] = max(dp_max_heights[i], dp_max_heights[j] + box[i][2])
					if original != dp_max_heights[i]:
						dp_indexes[i] = j
			maxi = max(maxi, dp_max_heights[i])
		return maxi


class Solution:

	def maxHeight(self, height, width, length, n):
		arr = []
		for i in range(n):
			h = height[i]
			w = width[i]
			l = length[i]
			arr.append((h, w, l))
			arr.append((h, l, w))
			arr.append((w, h, l))
			arr.append((w, l, h))
			arr.append((l, h, w))
			arr.append((l, w, h))
		arr.sort(key=lambda x: x[1] * x[0])
		lps = [arr[i][-1] for i in range(6 * n)]
		for i in range(1, 6 * n):
			m = 0
			for j in range(i):
				b1 = arr[j]
				b2 = arr[i]
				if b1[0] < b2[0] and b1[1] < b2[1]:
					m = max(m, lps[j])
			lps[i] = m + lps[i]
		return max(lps)


class Solution:

	def maxHeight(self, height, width, length, n):
		cuboid = []
		for i in range(n):
			cuboid.append([height[i], width[i], length[i]])
			cuboid[-1].sort()
			cuboid.append([cuboid[-1][1], cuboid[-1][2], cuboid[-1][0]])
			cuboid.append([cuboid[-1][2], cuboid[-1][1], cuboid[-1][0]])
		cuboid.sort()
		dp = [0] * (3 * n)
		dp[3 * n - 1] = cuboid[3 * n - 1][2]
		for i in range(3 * n - 2, -1, -1):
			dp[i] = cuboid[i][2]
			for j in range(i + 1, 3 * n):
				if cuboid[i][0] < cuboid[j][0] and cuboid[i][1] < cuboid[j][1]:
					dp[i] = max(dp[i], dp[j] + cuboid[i][2])
		return max(dp)


class box:

	def __init__(self, x, y, z):
		self.width = x
		self.length = y
		self.height = z

	def __lt__(self, other):
		return self.width * self.length < other.width * other.length

class Solution:

	def maxHeight(self, height, width, length, n):
		rot = []
		for x in range(n):
			(a, b, c) = (min(width[x], length[x]), max(width[x], length[x]), height[x])
			rot.append(box(a, b, c))
			rot.append(box(min(b, c), max(b, c), a))
			rot.append(box(min(a, c), max(a, c), b))
		rot.sort(reverse=True)
		n *= 3
		msh = [0 for x in range(n)]
		for i in range(n):
			msh[i] = rot[i].height
		for i in range(1, n):
			rw = rot[i].width
			rl = rot[i].length
			rh = rot[i].height
			for j in range(0, i):
				if rot[j].width > rw and rot[j].length > rl:
					if msh[i] < msh[j] + rh:
						msh[i] = msh[j] + rh
		return max(msh)


class Solution:

	def maxHeight(self, h, w, l, n):
		rotations = []
		for i in range(n):
			rot = [0] * 3
			_w = w[i]
			_l = l[i]
			_h = h[i]
			rot[2] = _w
			rot[1] = min(_l, _h)
			rot[0] = max(_l, _h)
			rotations.append(rot)
			rot = [0] * 3
			rot[2] = _h
			rot[1] = min(_l, _w)
			rot[0] = max(_l, _w)
			rotations.append(rot)
			rot = [0] * 3
			rot[2] = _l
			rot[1] = min(_h, _w)
			rot[0] = max(_h, _w)
			rotations.append(rot)
		rotations.sort(reverse=True, key=lambda X: X[0] * X[1])
		n = n * 3
		mh = [0] * n
		for i in range(n):
			mh[i] = rotations[i][2]
		for i in range(1, n):
			for j in range(0, i):
				if rotations[i][0] < rotations[j][0] and rotations[i][1] < rotations[j][1]:
					if mh[i] < mh[j] + rotations[i][2]:
						mh[i] = mh[j] + rotations[i][2]
		return max(mh)


class Solution:

	def maxHeight(self, height, width, length, n):
		box_list = []
		for i in range(n):
			box_list.append([width[i], length[i], height[i]])
		new_box_list = []
		for box in box_list:
			w = box[0]
			l = box[1]
			h = box[2]
			new_box_list.append([w, l, h])
			new_box_list.append([l, w, h])
			new_box_list.append([h, w, l])
			new_box_list.append([w, h, l])
			new_box_list.append([l, h, w])
			new_box_list.append([h, l, w])
		new_box_list = sorted(new_box_list, key=lambda x: x[0] * x[1])
		T = [x[2] for x in new_box_list]
		for i in range(1, len(T)):
			for j in range(i):
				if new_box_list[i][0] > new_box_list[j][0] and new_box_list[i][1] > new_box_list[j][1]:
					T[i] = max(T[i], T[j] + new_box_list[i][2])
		return max(T)


class Solution:

	def find_all_rotation(self, height, width, length, n):
		rot = []
		for i in range(n):
			(val1, val2, val3) = (width[i], length[i], height[i])
			rot.append([val1, val2, val3])
			rot.append([val1, val3, val2])
			rot.append([val2, val1, val3])
			rot.append([val2, val3, val1])
			rot.append([val3, val2, val1])
			rot.append([val3, val1, val2])
		return rot

	def maxHeight(self, height, width, length, n):
		rot = self.find_all_rotation(height, width, length, n)
		rot.sort(key=lambda x: -x[0] * x[1])
		msh = [rot[i][2] for i in range(6 * n)]
		max_ = rot[0][2]
		for i in range(1, 6 * n):
			for j in range(0, i):
				if rot[i][0] < rot[j][0] and rot[i][1] < rot[j][1]:
					msh[i] = max(msh[i], msh[j] + rot[i][2])
			max_ = max(max_, msh[i])
		return max_


from functools import cmp_to_key

def func(a, b):
	if a[0] * a[1] < b[0] * b[1]:
		return 1
	return -1

class Solution:

	def maxHeight(self, height, width, length, n):
		arr = []
		for i in range(n):
			arr.append([max(width[i], length[i]), min(width[i], length[i]), height[i]])
			arr.append([max(width[i], height[i]), min(width[i], height[i]), length[i]])
			arr.append([max(height[i], length[i]), min(height[i], length[i]), width[i]])
		arr = sorted(arr, key=cmp_to_key(func))
		dp = [arr[i][2] for i in range(len(arr))]
		for i in range(1, len(arr)):
			for j in range(i):
				if arr[i][0] < arr[j][0] and arr[i][1] < arr[j][1]:
					dp[i] = max(dp[i], arr[i][2] + dp[j])
		return max(dp)


class Solution:

	def maxHeight(self, a, b, c, n):
		x = set()
		for (i, j, k) in zip(a, b, c):
			x.add((i, j, k))
			x.add((i, k, j))
			x.add((j, i, k))
			x.add((j, k, i))
			x.add((k, i, j))
			x.add((k, j, i))
		x = sorted(x)
		l = len(x)
		dp = [1 for i in range(l)]
		for i in range(l - 1, -1, -1):
			s = 0
			for j in range(i + 1, l):
				if all((x[j][m] > x[i][m] for m in range(2))):
					s = max(s, dp[j])
			dp[i] = s + x[i][-1]
		return max(dp)


class Solution:

	def maxHeight(self, height, width, length, n):

		def solve(i, prev, dp, boxes):
			n = len(boxes)
			if i >= n:
				return 0
			if dp[i][prev + 1] != -1:
				return dp[i][prev + 1]
			ans = solve(i + 1, prev, dp, boxes)
			if prev == -1 or check(boxes[prev], boxes[i]):
				ans = max(ans, boxes[i][2] + solve(i, i, dp, boxes))
			dp[i][prev + 1] = ans
			return ans

		def check(prev_box, box):
			if box[0] < prev_box[0] and box[1] < prev_box[1]:
				return True
			else:
				return False

		def generate_permutations(box):
			perms = [(0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0)]
			boxes = []
			for perm in perms:
				new_box = [box[perm[0]], box[perm[1]], box[perm[2]]]
				boxes.append(new_box)
			return boxes
		boxes = []
		for i in range(n):
			box = []
			box.append(height[i])
			box.append(width[i])
			box.append(length[i])
			box = sorted(box)
			boxes = boxes + generate_permutations(box)
		boxes = sorted(boxes, key=lambda x: -x[1])
		boxes = sorted(boxes, key=lambda x: -x[0])
		dp = [[-1] * (n * 6 + 1) for i in range(n * 6 + 1)]
		prev = -1
		solve(0, prev, dp, boxes)
		return max(dp[0])


from math import inf

class Solution:

	def maxHeight(self, height, width, length, n):
		hwl = []
		for (l, h, w) in zip(length, width, height):
			hwl.append((max(l, w), min(l, w), h))
			hwl.append((max(h, w), min(h, w), l))
			hwl.append((max(l, h), min(l, h), w))
		hwl.sort(reverse=True)
		n = len(hwl)
		(memo, max_height) = ([None] * n, 0)
		for i in range(n):
			max_height = max(max_height, self.rec(hwl, memo, i))
		return max_height

	def rec(self, hwl, memo, i):
		if i >= len(hwl):
			return 0
		if memo[i] != None:
			return memo[i]
		(lh, wh, ht) = hwl[i]
		memo[i] = ht
		for j in range(i + 1, len(hwl)):
			(l, w, h) = hwl[j]
			if w < wh and l < lh:
				memo[i] = max(memo[i], ht + self.rec(hwl, memo, j))
		return memo[i]

	def combinations(self, arr, combs, used, comb):
		n = len(arr)
		if len(comb) == n:
			combs.append(list(comb))
			return
		for (i, num) in enumerate(arr):
			if used[i]:
				continue
			used[i] = True
			comb.append(num)
			self.combinations(arr, combs, used, comb)
			comb.pop()
			used[i] = False
		return combs


class Solution:

	def maxHeight(self, height, width, length, n):
		box_dim = []
		for i in range(n):
			box_dim.append([min(width[i], height[i]), max(width[i], height[i]), length[i]])
			box_dim.append([min(height[i], length[i]), max(height[i], length[i]), width[i]])
			box_dim.append([min(width[i], length[i]), max(width[i], length[i]), height[i]])
		dp = [0] * (3 * n)
		box_dim = sorted(box_dim, key=lambda x: x[0] * x[1])
		for i in range(3 * n):
			dp[i] = box_dim[i][2]
		for i in range(1, 3 * n):
			for j in range(i):
				if box_dim[j][0] < box_dim[i][0] and box_dim[j][1] < box_dim[i][1]:
					dp[i] = max(dp[i], dp[j] + box_dim[i][2])
		return max(dp)


class Solution:

	def generateRotations(self, x):
		(a, b, c) = x
		return [[a, b, c], [b, c, a], [c, a, b], [c, b, a], [b, a, c], [a, c, b]]

	def maxHeight(self, height, width, length, n):
		box = list(zip(height, width, length))
		rotatedbox = []
		for i in box:
			rotatedbox.extend(self.generateRotations(i))
		rotatedbox.sort(key=lambda x: x[0] * x[1])
		n = len(rotatedbox)
		dp = [0] * n
		for i in range(n):
			for j in range(i):
				if rotatedbox[j][1] < rotatedbox[i][1] and rotatedbox[j][0] < rotatedbox[i][0]:
					dp[i] = max(dp[i], dp[j] + rotatedbox[i][2])
			dp[i] = max(dp[i], rotatedbox[i][2])
		return max(dp)


class Solution:

	def maxHeight(self, height, width, length, n):

		def check(x1, y1, x2, y2):
			return x1 > x2 and y1 > y2
		arr = []
		for i in range(n):
			h = height[i]
			w = width[i]
			l = length[i]
			arr.append((l, w, h))
			arr.append((w, l, h))
			arr.append((w, h, l))
			arr.append((h, l, w))
			arr.append((h, w, l))
			arr.append((l, h, w))
		arr.sort(key=lambda x: x[0] * x[1], reverse=True)
		n = len(arr)
		dp = [i[2] for i in arr]
		for i in range(1, n):
			for j in range(i):
				if check(arr[j][0], arr[j][1], arr[i][0], arr[i][1]):
					dp[i] = max(dp[i], dp[j] + arr[i][2])
		return max(dp)


class Solution:

	def maxHeight(self, h, w, l, n):
		arr = []
		for i in range(n):
			arr.append([h[i], w[i], l[i]])
			arr.append([h[i], l[i], w[i]])
			arr.append([w[i], h[i], l[i]])
			arr.append([w[i], l[i], h[i]])
			arr.append([l[i], w[i], h[i]])
			arr.append([l[i], h[i], w[i]])
		arr.sort()
		n *= 6
		dp = [0] * n
		for i in range(n - 1, -1, -1):
			dp[i] = arr[i][2]
			for j in range(i, n):
				if arr[i][0] < arr[j][0] and arr[i][1] < arr[j][1]:
					dp[i] = max(dp[i], dp[j] + arr[i][2])
		return max(dp)


class Box:

	def __init__(self, h, w, l):
		self.h = h
		self.w = w
		self.l = l

class Solution:

	def maxHeight(self, height, width, length, n):
		box_list = []
		for i in range(n):
			temp_box = Box(height[i], min(width[i], length[i]), max(length[i], width[i]))
			box_list.append(temp_box)
			temp_box = Box(width[i], min(length[i], height[i]), max(length[i], height[i]))
			box_list.append(temp_box)
			temp_box = Box(length[i], min(width[i], height[i]), max(width[i], height[i]))
			box_list.append(temp_box)
		box_list.sort(key=lambda x: x.w * x.l, reverse=True)
		m = len(box_list)
		dp = [0 for i in range(m)]
		dp[0] = box_list[0].h
		max_height = dp[0]
		for i in range(1, m):
			dp[i] = box_list[i].h
			j = 0
			while j < i:
				if box_list[j].l > box_list[i].l and box_list[j].w > box_list[i].w:
					if dp[i] < dp[j] + box_list[i].h:
						dp[i] = dp[j] + box_list[i].h
				j += 1
			max_height = max(max_height, dp[i])
		return max_height


class Solution:

	def maxHeight(self, height, width, length, n):
		a = []
		for i in range(n):
			h = height[i]
			l = max(length[i], width[i])
			w = min(length[i], width[i])
			a.append([h, l, w])
			h = length[i]
			l = max(height[i], width[i])
			w = min(height[i], width[i])
			a.append([h, l, w])
			h = width[i]
			l = max(length[i], height[i])
			w = min(length[i], height[i])
			a.append([h, l, w])
		a.sort(key=lambda x: x[1] * x[2])
		n = len(a)

		def cal(index, bottom_ind):
			if index < 0:
				return 0
			if dp[index] != -1:
				return dp[index]
			h = 0
			for i in range(index, -1, -1):
				if bottom_ind == -1 or (a[i][1] < a[bottom_ind][1] and a[i][2] < a[bottom_ind][2]):
					h = max(h, cal(i - 1, i) + a[i][0])
			dp[index] = h
			return dp[index]
		dp = [-1 for i in range(n)]
		return cal(n - 1, -1)


class Solution:

	def maxHeight(self, height, width, length, n):
		l = []
		for (i, j, k) in zip(height, width, length):
			l.append((i, j, k))
			l.append((j, k, i))
			l.append((k, i, j))
		dp = [[-1 for i in range(101)] for j in range(101)]

		def dfs(a, b):
			ans = 0
			if dp[a][b] != -1:
				return dp[a][b]
			for (i, j, k) in l:
				if max(i, j) > max(a, b) and min(i, j) > min(a, b):
					ans = max(ans, k + dfs(i, j))
			dp[a][b] = ans
			return ans
		return dfs(0, 0)


class Solution:

	def maxHeight(self, height, width, length, n):
		arr = []
		for i in range(n):
			h = height[i]
			w = width[i]
			l = length[i]
			arr.append([l, w, h])
			arr.append([w, l, h])
			arr.append([l, h, w])
			arr.append([h, l, w])
			arr.append([w, h, l])
			arr.append([h, w, l])
		arr.sort(reverse=True)
		dp = [0] * (6 * n)
		for i in range(6 * n):
			dp[i] = arr[i][2]
		ans = -1
		for i in range(1, 6 * n):
			for j in range(0, i):
				if arr[i][0] < arr[j][0] and arr[i][1] < arr[j][1]:
					dp[i] = max(dp[i], dp[j] + arr[i][2])
			ans = max(ans, dp[i])
		return ans


class Solution:

	def maxHeight(self, h, w, l, n):
		a = []
		for i in range(n):
			a += [[l[i], w[i], h[i]], [l[i], h[i], w[i]], [w[i], h[i], l[i]], [w[i], l[i], h[i]], [h[i], l[i], w[i]], [h[i], w[i], l[i]]]
		a.sort(reverse=True)
		ans = a[0][2]
		for i in range(1, len(a)):
			x = a[i][2]
			for j in range(i):
				if a[i][0] < a[j][0] and a[i][1] < a[j][1]:
					a[i][2] = max(a[i][2], x + a[j][2])
			ans = max(ans, a[i][2])
		return ans


class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = []
		for (l, b, h) in zip(height, width, length):
			(l, b, h) = sorted([l, b, h], reverse=True)
			boxes.append((l, b, h))
			boxes.append((l, h, b))
			boxes.append((b, h, l))
		boxes.sort()
		box_l = []
		d = {}
		for i in boxes:
			(l, b, h) = i
			if (l, b) not in d:
				box_l.append((l, b))
				d[l, b] = h
			else:
				d[l, b] = max(d[l, b], h)
		for i in range(1, len(box_l)):
			temp = [0]
			b1 = box_l[i]
			for j in range(i):
				b2 = box_l[j]
				if b1[0] > b2[0] and b1[1] > b2[1]:
					temp.append(d[b2])
			d[b1] += max(temp)
		return max(d.values())


class Solution:

	def maxHeight(self, h, w, l, n):
		arr = []
		for i in range(len(h)):
			arr.append((l[i], w[i], h[i]))
			arr.append((l[i], h[i], w[i]))
			arr.append((h[i], w[i], l[i]))
		arr.sort(key=lambda x: x[0] * x[1], reverse=True)
		dp = [arr[i][2] for i in range(len(arr))]
		for i in range(1, len(dp)):
			for j in range(i):
				if arr[i][0] < arr[j][0] and arr[i][1] < arr[j][1] or (arr[i][1] < arr[j][0] and arr[i][0] < arr[j][1]):
					dp[i] = max(dp[i], dp[j] + arr[i][2])
		return max(dp)


from functools import cmp_to_key

def comp(a, b):
	if b[0] * b[1] > a[0] * a[1]:
		return 1
	else:
		return -1

class Solution:

	def maxHeight(self, height, width, length, n):
		arr = []
		for i in range(n):
			if height[i] > width[i]:
				arr.append([height[i], width[i], length[i]])
			else:
				arr.append([width[i], height[i], length[i]])
			if height[i] > length[i]:
				arr.append([height[i], length[i], width[i]])
			else:
				arr.append([length[i], height[i], width[i]])
			if width[i] > length[i]:
				arr.append([width[i], length[i], height[i]])
			else:
				arr.append([length[i], width[i], height[i]])
		arr = sorted(arr, key=cmp_to_key(comp))
		ans = [arr[i][2] for i in range(len(arr))]
		ans[0] = arr[0][2]
		for i in range(1, len(arr)):
			for j in range(i):
				if arr[i][0] < arr[j][0] and arr[i][1] < arr[j][1]:
					ans[i] = max(ans[i], ans[j] + arr[i][2])
		return max(ans)


class Solution:

	def maxHeight(self, height, width, length, n):
		boxes = []
		for i in range(n):
			x = height[i]
			y = width[i]
			z = length[i]
			boxes.append([x, [y, z]])
			boxes.append([x, [z, y]])
			boxes.append([y, [x, z]])
			boxes.append([y, [z, x]])
			boxes.append([z, [x, y]])
			boxes.append([z, [y, x]])
		boxes = sorted(boxes, key=lambda a: a[1][0])
		dp = [0 for i in range(len(boxes))]
		ans = 0
		for i in range(len(boxes)):
			dp[i] = boxes[i][0]
			for j in range(i):
				if boxes[i][1][0] > boxes[j][1][0] and boxes[i][1][1] > boxes[j][1][1]:
					dp[i] = max(dp[i], boxes[i][0] + dp[j])
			ans = max(ans, dp[i])
		return ans


class Solution:

	def maxHeight(self, height, width, length, n):
		import heapq
		from functools import cmp_to_key

		def compare(c1, c2):
			if c1[1] * c1[2] > c2[1] * c2[2]:
				return 1
			else:
				return -1
		C = []
		for (h, w, l) in zip(height, width, length):
			C.append([h, w, l])
			C.append([w, h, l])
			C.append([l, w, h])
		C = sorted(C, key=cmp_to_key(compare))
		dp = [0] * len(C)
		dp[0] = C[0][0]
		for i in range(1, len(C)):
			dp[i] = C[i][0]
			for j in range(i):
				if C[j][1] < C[i][1] and C[j][2] < C[i][2] or (C[j][2] < C[i][1] and C[j][1] < C[i][2]):
					dp[i] = max(dp[i], C[i][0] + dp[j])
		return max(dp)


class Box:

	def __init__(self, h, w, d):
		self.h = h
		self.w = w
		self.d = d

	def __lt__(self, other):
		return self.d * self.w < other.d * other.w

class Solution:

	def maxHeight(self, height, width, length, n):
		rot = [Box(0, 0, 0) for _ in range(3 * n)]
		index = 0
		for i in range(n):
			rot[index].h = height[i]
			rot[index].d = max(length[i], width[i])
			rot[index].w = min(length[i], width[i])
			index += 1
			rot[index].h = width[i]
			rot[index].d = max(height[i], length[i])
			rot[index].w = min(height[i], length[i])
			index += 1
			rot[index].h = length[i]
			rot[index].d = max(height[i], width[i])
			rot[index].w = min(height[i], width[i])
			index += 1
		n *= 3
		rot.sort(reverse=True)
		msh = [0] * n
		for i in range(n):
			msh[i] = rot[i].h
		for i in range(1, n):
			for j in range(0, i):
				if rot[i].w < rot[j].w and rot[i].d < rot[j].d:
					if msh[i] < msh[j] + rot[i].h:
						msh[i] = msh[j] + rot[i].h
		maxm = -1
		for i in range(n):
			maxm = max(maxm, msh[i])
		return maxm


class Solution:

	def maxHeight(self, h, w, l, n):
		rotations = []
		for i in range(n):
			rot = [0] * 3
			_w = w[i]
			_l = l[i]
			_h = h[i]
			rot[2] = _w
			rot[1] = min(_l, _h)
			rot[0] = max(_l, _h)
			rotations.append(rot)
			rot = [0] * 3
			rot[2] = _h
			rot[1] = min(_l, _w)
			rot[0] = max(_l, _w)
			rotations.append(rot)
			rot = [0] * 3
			rot[2] = _l
			rot[1] = min(_h, _w)
			rot[0] = max(_h, _w)
			rotations.append(rot)
		rotations.sort(reverse=True, key=lambda X: X[0] * X[1])
		n = n * 3
		mh = [0] * n
		for i in range(n):
			mh[i] = rotations[i][2]
		for i in range(1, n):
			for j in range(0, i):
				if rotations[i][0] < rotations[j][0] and rotations[i][1] < rotations[j][1]:
					if mh[i] < mh[j] + rotations[i][2]:
						mh[i] = mh[j] + rotations[i][2]
		return max(mh)
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = int(input())
		height = list(map(int, input().strip().split()))
		width = list(map(int, input().strip().split()))
		length = list(map(int, input().strip().split()))
		ob = Solution()
		print(ob.maxHeight(height, width, length, n))