Problem: Matryoshka

Matryoshka is a famous Russian folk craft doll. Matryoshka can be divided into upper and lower parts, and when opened, there is another smaller doll inside. The nesting structure is such that when the small doll that appears is opened, a smaller doll is contained.

<image>


You found an unusually shaped matryoshka doll on your trip and bought N dolls. The shape of the i-th doll is a rectangular parallelepiped of xi × yi × zi.

After watching Matryoshka for a while, you are about to put away Matryoshka. Before that, I want to reduce the space required by storing some dolls in another. When storing a doll, one other doll can be stored only in the doll that has not yet stored any doll. However, only the dolls that are stored directly are counted, and the doll that contains the doll can be stored in another doll.

The stored doll becomes invisible from the outside. However, the following conditions must be met.

* The doll may rotate, but each side of the rectangular parallelepiped is parallel to any side of the other rectangular parallelepiped.
* After rotation, the length of the doll on the side to be stored is shorter for each of the lengths of the corresponding sides.
* At most one doll can be stored directly in one doll



Since the volume of the closet is limited, we want to minimize the sum of the volumes of the dolls that can be seen from the outside. Your job is to create a program that finds the minimum sum of the volumes of the dolls that are visible from the outside, which can be achieved by repeating the operation of storing the dolls any number of times.

Input

The input consists of multiple datasets. The maximum number of data sets does not exceed 50. Each dataset is represented in the following format.

> N
> x1 y1 z1
>::
>::
> xN yN zN
>

Each dataset consists of N + 1 rows, and the first row of the dataset is given the integer N, which represents the number of dolls. In the i-th line of the following N lines, three integers xi, yi, and zi representing the size of the i-th doll are given, separated by a half-width space. These integers satisfy 1 ≤ N, xi, yi, zi ≤ 100.

> The end of the input is represented by a single zero line.

> ### Output

For each data set, output the minimum value of the sum of the volumes of the dolls that can be seen from the outside in one line.

> ### Sample Input


2
one two Three
4 2 3
3
2 5 2
3 3 4
5 5 5
Five
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
Five
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
Ten
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
3 2 3
8 4 6
2 6 4
3 3 8
3 2 7
0


Output for Sample Input


twenty four
145
125
15
864





Example

Input

2
1 2 3
4 2 3
3
2 5 2
3 3 4
5 5 5
5
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
5
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1
10
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
3 2 3
8 4 6
2 6 4
3 3 8
3 2 7
0


Output

24
145
125
15
864

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 305


//辺を表す構造体{行先、容量、コスト、逆辺のインデックス}
struct Edge{
	Edge(int arg_to,int arg_capacity,int arg_cost,int arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		cost = arg_cost;
		rev_index = arg_rev_index;
	}

	int to,capacity,cost,rev_index;
};

struct Info{
	int x,y,z;
};

int N;
int V; //頂点数
int in_index[105],out_index[105];
int dist[NUM]; //最短距離
int pre_node[NUM],pre_edge[NUM]; //直前の頂点と辺
vector<Edge> G[NUM]; //グラフの隣接リスト表現
Info info[105];


//fromからtoへ向かう容量capacity,コストcostの辺をグラフに追加する
void add_edge(int from,int to,int capacity,int cost){
	G[from].push_back(Edge(to,capacity,cost,G[to].size()));
	G[to].push_back(Edge(from,0,-cost,G[from].size()-1));
}

//sourceからsinkへの、流量flowの最小費用流を求める
//流せない場合は-1を返す
int min_cost_flow(int source,int sink,int flow){
	int ret = 0;
	while(flow > 0){
		//ベルマンフォード方により、source-sink間最短経路を求める
		for(int i = 0; i < V; i++)dist[i] = BIG_NUM;
		dist[source] = 0;
		bool update = true;
		while(update){
			update = false;
			for(int node_id = 0; node_id < V; node_id++){
				if(dist[node_id] == BIG_NUM)continue;
				for(int i = 0; i < G[node_id].size(); i++){
					Edge &e = G[node_id][i];
					if(e.capacity > 0 && dist[e.to] > dist[node_id]+e.cost){
						dist[e.to] = dist[node_id]+e.cost; //node_idを経由した方が早い場合
						pre_node[e.to] = node_id;
						pre_edge[e.to] = i;
						update = true;
					}
				}
			}
		}

		if(dist[sink] == BIG_NUM){
			//これ以上流せない
			return -1;
		}

		//source-sink間最短路に沿って目いっぱい流す
		int tmp_flow = flow;
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			tmp_flow = min(tmp_flow,G[pre_node[node_id]][pre_edge[node_id]].capacity);
		}
		flow -= tmp_flow;
		ret += tmp_flow*dist[sink];
		for(int node_id = sink; node_id != source; node_id = pre_node[node_id]){
			Edge &e = G[pre_node[node_id]][pre_edge[node_id]];
			e.capacity -= tmp_flow;
			G[node_id][e.rev_index].capacity += tmp_flow;
		}
	}
	return ret;
}

void func(){

	for(int i = 0; i < NUM; i++)G[i].clear();

	for(int i = 0; i < N; i++){

		scanf("%d %d %d",&info[i].x,&info[i].y,&info[i].z);
	}

	int source = 0,sink = 1,index = 2;

	for(int i = 0; i < N; i++){

		in_index[i] = index++;
		add_edge(source,in_index[i],1,0);
		add_edge(in_index[i],sink,1,info[i].x*info[i].y*info[i].z);
	}

	for(int i = 0; i < N; i++){

		out_index[i] = index++;
		add_edge(out_index[i],sink,1,0); //★★コスト0用ノード★★
	}

	for(int i = 0; i < N; i++){
		//自分を仕舞える人形に辺を張る
		for(int k = 0; k < N; k++){
			if((info[i].x < info[k].x && info[i].y < info[k].y && info[i].z < info[k].z) ||
				(info[i].x < info[k].x && info[i].y < info[k].z && info[i].z < info[k].y) ||
				(info[i].x < info[k].y && info[i].y < info[k].x && info[i].z < info[k].z) ||
				(info[i].x < info[k].y && info[i].y < info[k].z && info[i].z < info[k].x) ||
				(info[i].x < info[k].z && info[i].y < info[k].x && info[i].z < info[k].y) ||
				(info[i].x < info[k].z && info[i].y < info[k].y && info[i].z < info[k].x)
			){
				add_edge(in_index[i],out_index[k],1,0); //仕舞われることを、コスト0の辺で表す
			}
		}
	}

	V = index;

	printf("%d\n",min_cost_flow(source,sink,N));
}

int main(){

	while(true){

		scanf("%d",&N);
		if(N == 0)break;

		func();
	}

	return 0;
}