// When we're in drama,
// there's that person over there
// polishing their skill.
// 抗えぬ運命と決まっているのなら
// 私はあなたの為に生きたい
// 誰かの為に生きてこその人生
// 輝を増すこと知っているから
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// Pragmas
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// Namespaces
using namespace std;
using namespace __gnu_pbds;
// Data types
using si = short int;
using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ld = long double;
// Pairs
using pii = pair<int, int>;
using psi = pair<si, si>;
using pll = pair<ll, ll>;
using plll = pair<lll, lll>;
using pld = pair<ld, ld>;
#define fi first
#define se second
// PBDS
template<typename Z>
using ordered_set = tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>;
// Various outputs
template<typename Y, typename Z>
ostream& operator<<(ostream &os, const pair<Y, Z> &p) {
return os << "(" << p.fi << ", " << p.se << ")";
}
template<typename RZ>
ostream& operator<<(ostream &os, const tuple<RZ, RZ> &r) {
os << "{"; bool _first = 1;
for (RZ i = get<0>(r); i != get<1>(r); i++) {
if (!_first) os << ", ";
os << *i; _first = 0;
}
return os << "}";
}
template<typename Z>
ostream& operator<<(ostream &os, const vector<Z> &v) {
return os << make_tuple(v.begin(), v.end());
}
// Quick macro functions
#define sqr(x) ((x)*(x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(v, x) cout << #v << "[" << (x) << "] = " << (v[x]) << '\n'
#define rrebug(x) cerr << #x << " = " << (x) << '\n'
#define rrebugV(v, x) cerr << #v << "[" << (x) << "] = " << (v[x]) << '\n'
#define All(x) x.begin(), x.end()
#define Sort(x) sort(All(x))
#define Reverse(x) reverse(All(x))
#define Uniqueify(x) Sort(x); x.erase(unique(All(x)), x.end())
#define RandomSeed chrono::steady_clock::now().time_since_epoch().count()
#define MultipleTestcases int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++)
// Check min and max
template<typename Z> bool chmin(Z &a, Z b) {return (b < a) ? a = b, true : false;}
template<typename Z> bool chmax(Z &a, Z b) {return (b > a) ? a = b, true : false;}
// Modular arithmetic
template<int MOD>
class ModInt {
public:
int v;
ModInt() : v(0) {}
ModInt(long long _v) {
v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD));
if (v < 0) v += MOD;
}
friend bool operator==(const ModInt &a, const ModInt &b) {return a.v == b.v;}
friend bool operator!=(const ModInt &a, const ModInt &b) {return a.v != b.v;}
friend bool operator< (const ModInt &a, const ModInt &b) {return a.v < b.v;}
friend bool operator<=(const ModInt &a, const ModInt &b) {return a.v <= b.v;}
friend bool operator> (const ModInt &a, const ModInt &b) {return a.v > b.v;}
friend bool operator>=(const ModInt &a, const ModInt &b) {return a.v >= b.v;}
ModInt &operator+=(const ModInt &a) {if ((v += a.v) >= MOD) v -= MOD; return *this;}
ModInt &operator-=(const ModInt &a) {if ((v -= a.v) < 0) v += MOD; return *this;}
ModInt &operator*=(const ModInt &a) {v = 1ll * v * a.v % MOD; return *this;}
ModInt &operator/=(const ModInt &a) {return (*this) *= inverse(a);}
friend ModInt pow(ModInt a, long long x) {
ModInt res = 1;
for (; x; x /= 2, a *= a) if (x & 1) res *= a;
return res;
}
friend ModInt inverse(ModInt a) {return pow(a, MOD - 2);}
ModInt operator+ () const {return ModInt( v);}
ModInt operator- () const {return ModInt(-v);}
ModInt operator++() const {return *this += 1;}
ModInt operator--() const {return *this -= 1;}
friend ModInt operator+(ModInt a, const ModInt &b) {return a += b;}
friend ModInt operator-(ModInt a, const ModInt &b) {return a -= b;}
friend ModInt operator*(ModInt a, const ModInt &b) {return a *= b;}
friend ModInt operator/(ModInt a, const ModInt &b) {return a /= b;}
friend istream &operator>>(istream &is, ModInt &v) {return is >> v.v;}
friend ostream &operator<<(ostream &os, const ModInt &v) {return os << v.v;}
};
const int ModA = 998244353;
const int ModC = 1e9 + 7;
using MintA = ModInt<ModA>;
using MintC = ModInt<ModC>;
// Other constants
const ll INF = 1e18;
const ll iINF = 1e9;
const ld EPS = 1e-9;
const ld iEPS = 1e-6;
template<typename Z>
bool geomAbs(Z x) {
if (x < EPS) return x;
return x;
}
template<typename Z>
bool geomBetween(Z x, Z l, Z r) {
// l <= x <= r
if (l > r) swap(l, r);
return (l <= x + EPS) && (x <= r + EPS);
}
template<typename Z>
bool geomEqual(Z a, Z b) {
return geomBetween(a, b, b);
}
// Point
template<typename Z>
struct Point {
Z x, y;
Point(Z x = 0, Z y = 0) :
x(x), y(y)
{}
bool operator<(const Point<Z> &other) const {
if (x < other.x + EPS) return true;
if (x + EPS > other.x) return false;
return y < other.y + EPS;
}
bool operator==(const Point &other) const {
return geomEqual(x, other.x) && geomEqual(y, other.y);
}
friend istream& operator>>(istream &is, Point<Z> &P) {
return is >> P.x >> P.y;
}
};
template<typename Z>
struct Line {
Z a, b, c;
Line(Z a = 0, Z b = 0, Z c = 0) :
a(a), b(b), c(c)
{}
Line(Point<Z> P1, Point<Z> P2) {
if (P1 < P2) swap(P1, P2);
if (geomEqual(P1.x, P2.x)) {
a = 1;
b = 0;
c = -P1.x;
} else {
a = -(P1.y - P2.y) / (P1.x - P2.x);
b = 1;
c = -(a * P1.x) - P1.y;
}
}
Line(Point<Z> P, Z slope) {
a = -slope;
b = 1;
c = -(a * P.x) - P.y;
}
bool operator==(const Line &other) const {
return geomEqual(a, other.a) && geomEqual(b, other.b) && geomEqual(c, other.c);
}
ld slope() {
return -((ld)a / (ld)b);
}
};
struct Segtree {
struct Elm {
ll pf, sf, mx, sum;
Elm() {
pf = sf = mx = -INF;
sum = 0;
}
Elm(ll val) {
pf = sf = mx = max(val, 0ll);
sum = val;
}
};
Elm DEFAULT = Elm();
#define m ((l+r) >> 1)
#define lc (pos << 1)
#define rc (lc | 1)
int sz;
vector<Elm> seg;
Segtree(int sz) : sz(sz) {seg.assign((sz << 2) + 1, DEFAULT);}
void updateNode(int pos, ll val) {
seg[pos] = Elm(val);
}
Elm merge(Elm a, Elm b) {
Elm nw = Elm();
nw.pf = max({-INF, a.pf, a.sum + b.pf});
nw.sf = max({-INF, b.sf, b.sum + a.sf});
nw.mx = max({-INF, a.mx, b.mx, a.sf + b.pf});
nw.sum = a.sum + b.sum;
return nw;
}
void update(int pos, int l, int r, int idx, ll val) {
if (l == r) {
updateNode(pos, val);
return;
}
if (idx <= m) {update(lc, l, m, idx, val);}
else {update(rc, m+1, r, idx, val);}
seg[pos] = merge(seg[lc], seg[rc]);
}
void update(int idx, ll val) {update(1, 1, sz, idx, val);}
Elm query(int pos, int l, int r, int ql, int qr) {
if (l > r || ql > qr || ql > r || l > qr) {return DEFAULT;}
if (ql <= l && r <= qr) {return seg[pos];}
return merge(query(lc, l, m, ql, qr), query(rc, m+1, r, ql, qr));
}
Elm query(int ql, int qr) {return query(1, 1, sz, ql, qr);}
#undef m
#undef lc
#undef rc
};
bool _less(ld x, ld y) {return x - y < -EPS;}
bool _greater(ld x, ld y) {return x - y > EPS;}
using TempPoint = tuple<ll, ll, ll>; // {x, y, w}
const ld ld_infinity = (ld)1 / (ld)0;
const int maxN = 2'023;
int N;
TempPoint TP[maxN];
pll P[maxN];
ll W[maxN];
ld C[maxN][maxN];
vector<pii> pairs;
int pos[maxN];
ld getLineC(pll a, pll b) {
if (a.fi == b.fi) {
return -a.fi;
} else {
ld d = -(ld)(a.se - b.se) / (ld)(a.fi - b.fi);
ld c = -d * (ld)(a.fi) - (ld)a.se;
return c;
}
}
int compareSlope(pii a, pii b) {
pll A1 = P[a.fi], A2 = P[a.se];
pll B1 = P[b.fi], B2 = P[b.se];
bool a_inf = (A1.fi == A2.fi);
bool b_inf = (B1.fi == B2.fi);
if (a_inf && b_inf) return 0;
if (a_inf) return -1;
if (b_inf) return 1;
// (A2.y - A1.y) / (A1.x - A2.x) - (B2.y - B1.y) / (B1.x - B2.x)
// -> (A2.y - A1.y)(B1.x - B2.x) - (B2.y - B1.y)(A1.x - A2.x)
ll cur = (A2.se - A1.se) * (B1.fi - B2.fi) - (B2.se - B1.se) * (A1.fi - A2.fi);
if (cur < 0) return -1;
if (cur > 0) return 1;
return 0;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N;
for (int i = 1; i <= N; i++) {
auto &[x, y, w] = TP[i];
cin >> x >> y >> w;
}
sort(TP + 1, TP + N + 1);
for (int i = 1; i <= N; i++) {
auto &[x, y, w] = TP[i];
P[i] = {x, y};
W[i] = w;
}
for (int i = 1; i <= N; i++) {
for (int j = i; j <= N; j++) {
C[i][j] = getLineC(P[i], P[j]);
pairs.push_back({i, j});
}
}
sort(All(pairs), [&](const pii &a, const pii &b){
auto &[ai, aj] = a;
auto &[bi, bj] = b;
int cs = compareSlope(a, b);
if (cs == -1) return true;
if (cs == 1) return false;
if (_less(C[ai][aj], C[bi][bj])) return true;
if (_greater(C[ai][aj], C[bi][bj])) return false;
if (ai < bi) return true;
if (ai > bi) return false;
return aj < bj;
});
Segtree S(N);
for (int i = 1; i <= N; i++) {
pos[i] = i;
S.update(i, W[i]);
}
ll ans = S.query(1, N).mx;
int P = pairs.size();
for (int i = 0; i < P; i++) {
auto &[ci, cj] = pairs[i];
swap(pos[ci], pos[cj]);
S.update(pos[ci], W[ci]);
S.update(pos[cj], W[cj]);
bool process = true;
if (i < P-1) {
if (compareSlope(pairs[i], pairs[i+1]) != -1) {
process = false;
}
}
if (process) {
chmax(ans, S.query(1, N).mx);
}
}
cout << ans << "\n";
}
// あなたの傍に居させて...
// dibisakan
