#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); long long rand(long long l, long long r) { return uniform_int_distribution<long long>(l, r)(rd); } template <class T> int sgn(T x) { return (x > 0) - (x < 0); } template<class T> struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } friend ostream& operator<<(ostream& os, P p) { return os << "(" << p.x << "," << p.y << ")"; } }; struct Node { ll sum, pre, suf, ans; Node() : sum(0), pre(0), suf(0), ans(0) {} }; Node merge(Node a, const Node &b) { a.ans = max({a.ans, b.ans, a.suf + b.pre}); a.suf = max(b.suf, b.sum + a.suf); a.pre = max(a.pre, a.sum + b.pre); a.sum += b.sum; return a; } typedef Point<ll> P; const int N = 2005; int n, pos[N], rpos[N]; pair<P, int> a[N]; Node t[4 * N]; void upd(int i, int l, int r, int p, ll v) { if (l == r) { t[i].sum = v; t[i].pre = t[i].suf = t[i].ans = max(v, 0LL); return; } int mid = l + (r - l) / 2; if (p <= mid) upd(i * 2, l, mid, p, v); else upd(i * 2 + 1, mid + 1, r, p, v); t[i] = merge(t[i * 2], t[i * 2 + 1]); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL // freopen("TEST.inp", "r", stdin); // freopen("TEST.out", "w", stdout); #else // freopen("TEST.inp", "r", stdin); // freopen("TEST.out", "w", stdout); #endif cin >> n; rep(i, 1, n + 1) { cin >> a[i].first.x >> a[i].first.y >> a[i].second; } sort(a + 1, a + 1 + n, [&](const auto &F, const auto &S) { return F.first.y != S.first.y? F.first.y > S.first.y : F.first.x < S.first.x; }); // rep(i, 1, n + 1) { // cerr << i << " : " << a[i].first << '\n'; // } rep(i, 1, n + 1) { pos[i] = i; rpos[i] = i; upd(1, 1, n, i, a[i].second); } vector<pair<P, pii>> e; rep(i, 1, n) { rep(j, i + 1, n + 1) { P ang = a[i].first - a[j].first; e.push_back({ang, {i, j}}); } } sort(all(e), [&](const auto &F, const auto &S) { return F.first.cross(S.first) > 0; }); ll ans = 0; rep(i, 1, n + 1) { ans = max(ans, (ll)a[i].second); } // cerr << "DB>> " << t[1].ans << '\n'; // return 0; rep(i, 0, sz(e)) { int j = i; vector<pii> sp; while (j < sz(e) && !e[j].first.cross(e[i].first)) { sp.push_back(e[j].second); ++j; } --j; for (auto &p : sp) { p.first = pos[p.first]; p.second = pos[p.second]; if (p.first > p.second) swap(p.first, p.second); } sort(all(sp)); vector<pii> seg; int mx = 0; // cerr << "DB>> " << e[i].second.first << ' ' << e[i].second.second << '\n'; for (auto &p : sp) { // cerr << "swap " << p.first << ' ' << p.second << " : " << mx << '\n'; if (p.first > mx) seg.push_back(p); mx = max(mx, p.second); seg.back().second = mx; swap(rpos[p.first], rpos[p.second]); pos[rpos[p.first]] = p.first; pos[rpos[p.second]] = p.second; } // for (int i = 1; i <= n; ++i) { // cerr << rpos[i] << ' '; // } // cerr << '\n'; for (auto &[l, r] : seg) { ll sum = 0; rep(z, l, r + 1) { sum += a[rpos[z]].second; upd(1, 1, n, z, 0); } // cerr << l << ' ' << r << '\n'; upd(1, 1, n, l, sum); } ans = max(ans, t[1].ans); // cerr << ans << '\n'; // cerr << "\n\n"; for (auto &[l, r] : seg) { rep(z, l, r + 1) { upd(1, 1, n, z, a[rpos[z]].second); } } i = j; } cout << ans << '\n'; return 0; }