#include #define VARNAME(x) #x #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; using ld = long double; template vector Vec(int n, T v) { return vector(n, v); } template auto Vec(int n, Args... args) { auto val = Vec(args...); return vector(n, move(val)); } template ostream& operator<<(ostream& os, const vector& v) { os << "sz:" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } constexpr ll MOD = (ll)1e9 + 7LL; constexpr ld PI = static_cast(3.1415926535898); template constexpr T INF = numeric_limits::max() / 10; struct CostGraph { using T = ll; CostGraph(const int v) : V{v} { edge.resize(v); rev_edge.resize(v); } struct Edge { Edge(const int from, const int to, const T cost) : from{from}, to{to}, cost{cost} {} const int from; const int to; const T cost; bool operator<(const Edge& e) const { return cost != e.cost ? cost < e.cost : to < e.to; } }; void addEdge(const int from, const int to, const T cost = 1) { edge[from].push_back(Edge{from, to, cost}); rev_edge[to].push_back(Edge(to, from, cost)); } vector> edge; vector> rev_edge; const int V; }; bool BellmanFord(const CostGraph& g, const int s, vector& d) { using T = CostGraph::T; assert(s < g.V); assert(d.size() == g.V); for (int i = 0; i < g.V; i++) { d[i] = INF; } d[s] = 0; bool no_negative_loop = true; for (int i = 0; i < g.V; i++) { for (int v = 0; v < g.V; v++) { if (d[v] != INF) { for (const auto& e : g.edge[v]) { if (d[e.to] > d[e.from] + e.cost) { d[e.to] = d[v] + e.cost; if (i == g.V - 1) { d[e.to] = -INF; // Confirm " -INF < min(possible_cost) * V " no_negative_loop = false; } } } } } } return no_negative_loop; } struct Box { Box(ll x, ll y, ll z) : x(x), y(y), z(z) {} ll x, y, z; }; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector box; for (int i = 0; i < N; i++) { ll x, y, z; cin >> x >> y >> z; box.push_back(Box(x, y, z)); } CostGraph g(N + 2); const int s = N; const int t = N + 1; for (int i = 0; i < N; i++) { g.addEdge(s, i, -1); g.addEdge(i, t, 0); for (int j = 0; j < N; j++) { vector v{box[j].x, box[j].y, box[j].z}; do { if (box[i].x > v[0] and box[i].y > v[1] and box[i].z > v[2]) { g.addEdge(i, j, -1); break; } if (box[i].x == v[0] and box[i].y == v[1] and box[i].z == v[2]) { if (i < j) { g.addEdge(i, j, -1); } break; } } while (next_permutation(v.begin(), v.end())); } } vector d(N + 2, INF); BellmanFord(g, s, d); cout << -d[t] << endl; return 0; }