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:
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define int long long int
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
typedef pair<int, int> pii;
typedef long long ll;
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;

// Ford-Fulkerson 法による 最大流 O( F |E| )
// Bellman-Ford 法による 最小費用流 O( F |V| |E| )
// [条件に注意] Dijkstra 法による 最小費用流 O( F |E| log |V| )
// Verified: AOJ GRL_6_A (Maximum Flow)
// Verified: AOJ GRL_6_B (Minimum Cost Flow)

// 行き先と容量と逆辺のインデックスを記録する構造体
// 通常のグラフの辺の構造体と異なるため注意

template <typename Type>
struct Edge {
    int to; Type cap, cost; int rev;
    Edge(int t, Type c, int r) : to(t), cap(c), rev(r) {}
    Edge(int t, Type ca, Type co, int r) : to(t), cap(ca), cost(co), rev(r) {}
};

template <typename Type>
using Graph = vector< vector< Edge<Type> > >;

template <typename Type>
struct Flow {
    vector< vector< Edge<Type> > > G;
    const Type MAXC = 1 << 30;
    int n;
    vector<bool> used;
    vector<int> prevv, preve, dist;
    Flow(int _n) : G(_n), n(_n), used(_n, false), 
        prevv(_n), preve(_n), dist(_n, MAXC) {}

    // G[e.to][e.rev] で逆辺を操作できる
    void add_edge(int from, int to, Type cap) {
        G[from].push_back(Edge<Type>(to, cap, G[to].size()));
        G[to].push_back(Edge<Type>(from, 0, G[from].size() - 1));
    }
    void add_edge(int from, int to, Type cap, Type cost) {
        G[from].push_back(Edge<Type>(to, cap, cost, G[to].size()));
        G[to].push_back(Edge<Type>(from, 0, -cost, G[from].size() - 1));
    }

    Type dfs(int v, int t, Type f) {
        if(v == t) return f;
        used[v] = true;
        for(int i=0; i < G[v].size(); i++) {
            Edge<Type> &e = G[v][i];
            if(!used[e.to] && e.cap > 0) {
                Type d = dfs(e.to, t, min(f, e.cap));
                if(d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    Type max_flow(int s, int t) {
        Type flow = 0;
        while(1) {
            fill(used.begin(), used.end(), false);
            Type f = dfs(s, t, INF);
            if(f == 0) return flow;
            flow += f;
        }
    }

    // ベルマンフォード法で最小費用流を解く
    // 負辺や負閉路があるときは基本的にこちらのほうが確実
    Type mincost_flow(int s, int t, Type f) {
        Type res = 0;
        Type ma = MAXC;
        while(f > 0) {
            fill(dist.begin(), dist.end(), ma);
            dist[s] = 0;
            bool update = true;
            while(update) {
                update = false;
                for(int v = 0; v < n; v++) {
                    if(dist[v] == ma) continue;
                    for(int i=0; i<G[v].size(); i++) {
                        Edge<Type> &e = G[v][i];
                        if(e.cap>0 && dist[e.to] > dist[v] + e.cost) {
                            dist[e.to] = dist[v] + e.cost;
                            prevv[e.to] = v;
                            preve[e.to] = i;
                            update = true;
                        }
                    }
                }
            }

            if(dist[t] == ma) return -1;
            Type d = f;
            for(int v = t; v != s; v = prevv[v]) {
                d = min(d, G[prevv[v]][preve[v]].cap);
            }
            f -= d;
            res += d * dist[t];
            for(int v = t; v != s; v = prevv[v]) {
                Edge<Type> &e = G[prevv[v]][preve[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return res;
    }

    // ポテンシャルの導入により、ダイクストラ法で最小費用流を解く
    // [仮定している条件]
    //     1. グラフに負の閉路が存在しない (流量の 0 初期化のため)
    //        もし存在するならベルマンフォードで負の閉路を見つけ
    //        そこに流せるだけ流してスタート
    //     2. グラフに負の辺が存在しない (pot_0 の計算可能性)
    //        もし存在する場合は最初のみベルマンフォードを使う必要あり
    Type fast_mincost_flow(int s, int t, Type f) {
        Type res = 0, ma = MAXC;
        vector<Type> pot(n);
        while(f > 0) {
            using PT = pair<Type, int>;
            priority_queue< PT, vector<PT>, greater<PT> > que;
            fill(dist.begin(), dist.end(), ma);

            dist[s] = 0;
            que.push(make_pair(0, s));
            while(!que.empty()) {
                PT cur = que.top(); que.pop();
                int v = cur.second;
                if(dist[v] < cur.first) continue;
                for(size_t i=0; i<G[v].size(); i++) {
                    Edge<Type>& e = G[v][i];
                    if(e.cap > 0 and dist[e.to] > dist[v] + e.cost + pot[v] - pot[e.to]) {
                        dist[e.to] = dist[v] + e.cost + pot[v] - pot[e.to];
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        que.push(make_pair(dist[e.to], e.to));
                    }
                }
            }
            if(dist[t] == ma) {
                return -1;
            }
            for(int v=0; v<n; v++) pot[v] += dist[v];

            Type d = f;
            for(int v=t; v!=s; v=prevv[v]) {
                d = min(d, G[prevv[v]][preve[v]].cap);
            }
            f -= d;
            res += d * pot[t];
            for(int v=t; v!=s; v=prevv[v]) {
                Edge<Type>& e = G[prevv[v]][preve[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return res;
    }
};


signed main() {
    int N;
    while(cin >> N, N) {
        vector< vector<int> > mats(N);

        int sum = 0;
        for(int i=0; i<N; i++) {
            vector<int> v(3);
            for(int k=0; k<3; k++) cin >> v[k];
            sort(v.begin(), v.end());
            mats[i] = v;
            sum += v[0] * v[1] * v[2];
        }

        int source = 2*N, sink = source + 1;
        auto construct = [&]() {
            Flow<int> fl(2*N + 2);
            fl.add_edge(source, sink, N, 0);
            for(int i=0; i<N; i++) {
                fl.add_edge(source, i, 1, 0);
                fl.add_edge(N+i, sink, 1, 0);
            }

            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    if(i == j) continue;
                    bool ok = true;
                    for(int k=0; k<3; k++) {
                        ok &= (mats[i][k] > mats[j][k]);
                    }
                    if(ok) {
                        int V = mats[j][0] * mats[j][1] * mats[j][2];
                        fl.add_edge(i, N+j, 1, -V);
                    }
                }
            }
            return fl;
        };

        int mincost;
        {
            Flow<int> fl = construct();
            mincost = fl.mincost_flow(source, sink, N);
        }
        cout << sum + mincost << endl;
    }
    return 0;
}