Problem: At the foot of Liyushan Mountain, n tents will be carefully arranged to provide accommodation for those who are willing to experience the joy of approaching nature, the tranquility of the night, and the bright starry sky.

The i-th tent is located at the point of (x_i, y_i) and has a weight of w_i. A tent is important if and only if both x_i and y_i are even. You need to remove some tents such that for each remaining important tent (x, y), there do not exist 3 other tents (x'_1, y'_1), (x'_2, y'_2) and (x'_3, y'_3) such that both conditions are true: 

  1. |x'_j-x|, |y'_j - y|≤ 1 for all j ∈ \{1, 2, 3\}, and 
  2. these four tents form a parallelogram (or a rectangle) and one of its sides is parallel to the x-axis. 



Please maximize the sum of the weights of the tents that are not removed. Print the maximum value.

Input

The first line contains a single integer n (1≤ n≤ 1 000), representing the number of tents.

Each of the next n lines contains three integers x_i, y_i and w_i (-10^9≤ x_i,y_i ≤ 10^9, 1≤ w_i≤ 10^9), representing the coordinate of the i-th tent and its weight. No two tents are located at the same point.

Output

A single integer — the maximum sum of the weights of the remaining tents.

Examples

Input


5
0 0 4
0 1 5
1 0 3
1 1 1
-1 1 2


Output


12


Input


32
2 2 1
2 3 1
3 2 1
3 3 1
2 6 1
2 5 1
3 6 1
3 5 1
2 8 1
2 9 1
1 8 1
1 9 1
2 12 1
2 11 1
1 12 1
1 11 1
6 2 1
7 2 1
6 3 1
5 3 1
6 6 1
7 6 1
5 5 1
6 5 1
6 8 1
5 8 1
6 9 1
7 9 1
6 12 1
5 12 1
6 11 1
7 11 1


Output


24

Note

Here is an illustration of the second example. Black triangles indicate the important tents. This example also indicates all 8 forbidden patterns.

<image>

Solution (in CPP):

Solution:
#pragma GCC optimize ("O3", "unroll-loops")
// #pragma GCC target ("avx2")
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include "bits/stdc++.h"
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define distinct(x) sort(all(x)); x.resize(unique(all(x))-x.begin())
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define CASE(x) int x; cin >> x; while (x--)
#define CASEt(x) int x; cin >> x; for (int tc = 1; tc <= x; ++tc)
using namespace std;
namespace {
	const int MOD107 = 1000000007;
	const int MOD998 = 998244353;
	using ll = long long;
	using ull = unsigned long long;
	using pii = pair<int, int>;
	using pll = pair<ll, ll>;
	template <class T> using minheap = priority_queue<T, vector<T>, greater<T>>;
	template <class T> using maxheap = priority_queue<T, vector<T>, less<T>>;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//	mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
	struct Modular {
	private:
		long long MODVALUE = 0;
		long long val = 0;
 
		Modular initModular(long long val) const { return Modular(val, MODVALUE); }
 
	#ifdef LOCAL
		inline void validate() const {
			assert(MODVALUE != 0);
			assert(0 <= val && val < MODVALUE);
		}
 
		inline void validate(const Modular& other) const {
			validate();
			other.validate();
			assert(MODVALUE == other.MODVALUE);
		}
	#else
		inline void validate() const { }
		inline void validate(const Modular& other) const { }
	#endif
 
	public:
		explicit operator long long() const { return val; }
 
		template<class T> Modular& operator = (const T& other) { val = (other % MODVALUE + MODVALUE) % MODVALUE; return *this; }
		long long getMod() { return MODVALUE; }
		template<class T> void setMod(const T& MOD) { MODVALUE = MOD; }
 
		Modular& operator += (const Modular& other)       { validate(other); val += other.val; if (val >= MODVALUE) val -= MODVALUE; return *this; }
		Modular  operator +  (const Modular& other) const { Modular tmp = *this; return tmp += other; }
		template<class T> Modular& operator += (const T& other)       { return *this += initModular(other); }
		template<class T> Modular  operator +  (const T& other) const { return *this +  initModular(other); }
		template<class T> friend Modular operator + (const T& other, const Modular& m) { return m.initModular(other) + m; }
 
		Modular& operator ++()    { return *this += 1; }
		Modular  operator ++(int) { Modular tmp = *this; ++*this; return tmp; }
 
		Modular  operator -  () const { return initModular(-val); }
		Modular& operator -= (const Modular& other)       { validate(other); val -= other.val; if (val < 0) val += MODVALUE; return *this;}
		Modular  operator -  (const Modular& other) const { Modular tmp = *this; return tmp -= other; }
		template<class T> Modular& operator -= (const T& other)       { return *this -= initModular(other); }
		template<class T> Modular  operator -  (const T& other) const { return *this -  initModular(other); }
		template<class T> friend Modular operator - (const T& other, const Modular& m) { return m.initModular(other) - m; }
 
		Modular& operator --()    { return *this -= 1; }
		Modular  operator --(int) { Modular tmp = *this; --*this; return tmp; }
 
		Modular& operator *= (const Modular& other)       { validate(other); val *= other.val; val %= MODVALUE; if (val < 0) val += MODVALUE; return *this; }
		Modular  operator *  (const Modular& other) const { Modular tmp = *this; return tmp *= other; }
		template<class T> Modular& operator *= (const T& other)       { return *this *= initModular(other); }
		template<class T> Modular  operator *  (const T& other) const { return *this *  initModular(other); }
		template<class T> friend Modular operator * (const T& other, const Modular& m) { return m.initModular(other) * m; }
 
		Modular pow(long long power) const {
			Modular m = *this, ans = initModular(1);
			while (power) {
				if (power & 1) ans *= m;
				m *= m;
				power >>= 1;
			}
			return ans;
		}
		Modular pow(const Modular& other) const { return pow(other.val); }
		Modular inv() const { return pow(MODVALUE - 2); }
 
		Modular& operator /= (const Modular& other)       { val *= other.inv().val; val %= MODVALUE; if (val < 0) val += MODVALUE; return *this; }
		Modular  operator /  (const Modular& other) const { Modular tmp = *this; return tmp /= other; }
		template<class T> Modular& operator /= (const T& other)       { return *this /= initModular(other); }
		template<class T> Modular  operator /  (const T& other) const { return *this /  initModular(other); }
		template<class T> friend Modular operator / (const T& other, const Modular& m) { return m.initModular(other) / m; }
 
		friend istream& operator >> (istream& in, Modular& m) { in >> m.val; m.val %= m.MODVALUE; if (m.val < 0) m.val += m.MODVALUE; return in; }
		friend ostream& operator << (ostream& out, const Modular& m) { return out << m.val; }
 
		Modular() { val = 0; MODVALUE = 0; }
		Modular(long long val, long long MOD) : MODVALUE(MOD), val((val % MOD + MOD) % MOD) { }
	};
	using Mint = Modular;
	inline ll binpow(ll b, ll p, ll mod) {
		b %= mod;
		ll ans = 1;
		for (; p > 0; p >>= 1) {
			if (p&1) {ans *= b; ans %= mod;}
			b *= b;
			b %= mod;
		}
		return ans;
	}
	inline ll max(ll a, int b) { return (a > b ? a : b); }
	inline ll max(int a, ll b) { return (a > b ? a : b); }
	inline ll min(ll a, int b) { return (a < b ? a : b); }
	inline ll min(int a, ll b) { return (a < b ? a : b); }
	template <class T> inline bool chkmin(T&x, const T& y) { return y < x ? x = y, 1 : 0; }
	template <class T> inline bool chkmax(T&x, const T& y) { return x < y ? x = y, 1 : 0; }
}
namespace IO {
	template<class T> inline void _R(T &x) {cin >> x;}
	template<class T1, class T2> inline void _R(pair<T1,T2> &x) {_R(x.first); _R(x.second);}
	template<class T> inline void _R(vector<T> &x) {for (auto& i : x) _R(i);}
	template<class T> inline void _R(deque<T> &x) {for (auto& i : x) _R(i);}
	inline void R() {}
	template<class T1, class... T2> inline void R(T1 &x, T2 &...y) { _R(x); R(y...);}

	template<class T> inline void _W(const T& x);
	template<class T1, class T2> inline void _W(const pair<T1,T2>& p);
	template<class... T> inline void _W(const vector<T...>& x);
	template<class... T> inline void _W(const deque<T...>& x);
	template<class... T> inline void _W(const forward_list<T...>& x);
	template<class... T> inline void _W(const list<T...>& x);
	template<class... T> inline void _W(const set<T...>& x);
	template<class... T> inline void _W(const multiset<T...>& x);
	template<class... T> inline void _W(const unordered_set<T...>& x);
	template<class... T> inline void _W(const unordered_multiset<T...>& x);
	template<class... T> inline void _W(const map<T...>& x);
	template<class... T> inline void _W(const multimap<T...>& x);
	template<class... T> inline void _W(const unordered_map<T...>& x);
	template<class... T> inline void _W(const unordered_multimap<T...>& x);

	template<class Container> inline void printContainer(const Container& x) { bool isFirst = 1; for (auto i : x) { if (!isFirst) cout << ' '; isFirst = 0; _W(i); } }

	template<class T> inline void _W(const T& x) {cout << x;}
	template<class T1, class T2> inline void _W(const pair<T1,T2>& p) {_W(p.first); _W(' '); _W(p.second);}
	template<class... T> inline void _W(const vector<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const deque<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const forward_list<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const list<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const set<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const multiset<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const unordered_set<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const unordered_multiset<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const map<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const multimap<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const unordered_map<T...>& x) { printContainer(x); }
	template<class... T> inline void _W(const unordered_multimap<T...>& x) { printContainer(x); }

 	inline void W() {cout << '\n';}
	template<class T> inline void W(const T &x) {_W(x); W();}
	template<class T1, class... T2> inline void W(const T1 &x, const T2 &...y) { _W(x); _W(' '); W(y...);}
} using namespace IO;
namespace outputFormat{
	inline string Case(int tc) {return "Case #" + to_string(tc) + ':';}
	inline string YN(bool b) {return b ? "Yes" : "No";}
} using namespace outputFormat;
namespace std {
    template <class T1, class T2> struct hash<pair<T1,T2>> {
    	std::size_t operator()(pair<T1,T2> _) const {
        	return hash<T1>{}(_.first) ^ hash<T2>{}(_.second);
    	}
    };
}


template<class T>
struct dinic {
private:
	int size;
	int s, t;

	struct edge {
		int to;
		T possibleFlow;
		int rev;

		edge(int to, T possibleFlow, int rev) : to(to), possibleFlow(possibleFlow), rev(rev) {};
	};

	vector<vector<edge>> graph;
	vector<int> dist;
	vector<bool> isTrav;
	vector<int> cur;

	bool bfs() {
		for (int i = 0; i < size; i++) {isTrav[i] = 0; dist[i] = 0; cur[i] = 0;}

		queue<int> q;
		isTrav[s] = 1;
		q.push(s);
		while (!q.empty()) {
			int now = q.front();
			q.pop();

			for (int i = 0; i < (int)graph[now].size(); i++) {
				int toNode = graph[now][i].to;
				if (!isTrav[toNode] && graph[now][i].possibleFlow > 0) {
					isTrav[toNode] = 1;
					q.push(toNode);
					dist[toNode] = dist[now] + 1;
					if (toNode == t) return 1;
				}
			}
		}
		return 0;
	}

	T dfs(int node, T flow) {
		if (node == t) return flow;

		for (int& i = cur[node]; i < (int)graph[node].size(); i++) {
   			int toNode = graph[node][i].to;

			if (dist[toNode] == dist[node] + 1 && graph[node][i].possibleFlow > 0) {
				T toflow = dfs(toNode, min(flow, graph[node][i].possibleFlow));
				if (toflow) {
					graph[node][i].possibleFlow -= toflow;
					graph[toNode][graph[node][i].rev].possibleFlow += toflow;
					return toflow;
				}
   			}
		}
		return 0;
	}

public:
	T maxflow() {
		T flow = 0;
		while (bfs())
			while (true) {
				T newflow = dfs(s,1e14);
				if (newflow)
					flow += newflow;
				else
					break;
			}
		return flow;
	}

	void addedge(int u, int v, T f) {
		edge a(v,f,graph[v].size()), b(u,0,graph[u].size());
		graph[u].push_back(move(a));
		graph[v].push_back(move(b));
	}

	void addedge_undir(int u, int v, T f) {
		edge a(v,f,graph[v].size()), b(u,f,graph[u].size());
		graph[u].push_back(move(a));
		graph[v].push_back(move(b));
	}

	dinic(int size, int source, int sink) : size(size), s(source), t(sink) {
		graph.resize(size);
		dist.resize(size);
		isTrav.resize(size);
		cur.resize(size);
	}
};

int main() {
	int n; R(n);

	const int src = n * 2;
	const int sink = n * 2 + 1;
	dinic<ll> f(n * 2 + 2, src, sink);
	map<pii, int> m;
	ll totalW = 0;
	for (int i = 0; i < n; i++) {
		int r,c,w; R(r,c,w);
		m[make_pair(r, c)] = i * 2;
		f.addedge(i * 2, i * 2 + 1, w);
		totalW += w;
	}

	auto getType = [&](int r, int c) {
		int rt = (r & 1);
		int ct = (c & 1);
		if (rt == 1 && ct == 0) return 0;
		if (rt == 0 && ct == 0) return 1;
		if (rt == 0 && ct == 1) return 2;
		if (rt == 1 && ct == 1) return 3;
		assert(false);
	};

	const int dr[] = { -1, 1, 0, 0 };
	const int dc[] = { 0, 0, -1, 1 };
	const ll INF = 1e14;
	for (auto& v : m) {
		const int r = v.fi.fi;
		const int c = v.fi.se;
		const int in = v.se;
		const int out = v.se + 1;

		int ty = getType(r, c);
		for (int dir = 0; dir < 4; dir++) {
			int rr = r + dr[dir];
			int cc = c + dc[dir];
			if (getType(rr, cc) == ty + 1 && m.count({ rr, cc }))
				f.addedge(out, m[{ rr, cc }], INF);
		}

		if (ty == 0) f.addedge(src, in, INF);
		if (ty == 3) f.addedge(out, sink, INF);
	}

	W(totalW - f.maxflow());

	return 0;
}

static auto __init__ = [](){
#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0);
#endif
	cout << fixed << setprecision(10);
	return 42;
}();