#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int MX = 2e3+5;
const int INF = 2e18;
struct ndata
{
int L, R, S, T;
};
ndata create(int x)
{
ndata ret;
ret.L = ret.R = ret.S = max(x, 0ll);
ret.T = x;
return ret;
}
void rev(ndata &d)
{
swap(d.L, d.R);
return;
}
ndata merge(const ndata &d1, const ndata &d2)
{
ndata d3;
d3.L = max(d1.L, d1.T + d2.L);
d3.R = max(d2.R, d2.T + d1.R);
d3.S = max(max(d1.S, d2.S), d1.R + d2.L);
d3.T = d1.T + d2.T;
return d3;
}
struct seg_tree
{
vector<ndata> tree;
void build(const vector<int> &a, int id, int l, int r)
{
int m = (l+r)/2;
if(l == r)
{
tree[id] = create(a[m]);
return;
}
build(a, 2*id, l, m);
build(a, 2*id+1, m+1, r);
tree[id] = merge(tree[2*id], tree[2*id+1]);
return;
}
void init(int n, const vector<int> &a)
{
tree.resize(4*n+50);
build(a, 1, 1, n);
return;
}
void upd(int p, int val, int id, int l, int r)
{
if(l == r)
{
tree[id] = create(val);
return;
}
int m = (l+r)/2;
if(p <= m)
upd(p, val, 2*id, l, m);
else
upd(p, val, 2*id+1, m+1, r);
tree[id] = merge(tree[2*id], tree[2*id+1]);
return;
}
ndata Q(int ql, int qr, int id, int l, int r)
{
if(qr < l || r < ql)
return create(0);
if((ql <= l) && (r <= qr))
return tree[id];
int m = (l+r)/2;
ndata n1 = Q(ql, qr, 2*id, l, m);
ndata n2 = Q(ql, qr, 2*id+1, m+1, r);
return merge(n1, n2);
}
};
in sloppy(in pt1, in pt2)
{
in zz = {pt1[1]-pt2[1], pt1[0]-pt2[0]};
if(zz[1] < 0)
{
zz[1] = -zz[1];
zz[0] = -zz[0];
}
if(zz[1] == 0)
return {1, 0};
int g = __gcd(abs(zz[1]), abs(zz[0]));
zz[1]/=g;
zz[0]/=g;
return zz;
}
bool comp(array<int, 4> s1, array<int, 4> s2)
{
int XX = s1[0]*s2[1];
int YY = s2[0]*s1[1];
if(XX < YY)
return true;
if(XX > YY)
return false;
return (((in){s1[2], s1[3]}) < ((in){s2[2], s2[3]}));
}
int dot(in x1, in x2)
{
return x1[0]*x2[0] - x1[1]*x2[1];
}
vector<int> pa(MX, -1);
int leader(int u)
{
if(pa[u] < 0)
return u;
else
return pa[u] = leader(pa[u]);
}
void murder()
{
cout << "0\n";
exit(0);
return;
}
vector<in> cmp[MX];
bool active[MX];
vector<int> stuff;
vector<in> Tt;
vector<in> MOON;
vector<int> Spl;
void MERGE(int u, int v)
{
u = leader(u);
v = leader(v);
if(u == v)
return;
if(pa[u] < pa[v])
swap(u, v);
pa[v]+=pa[u];
pa[u] = v;
return;
}
signed main()
{
fast();
//murder();
int n; cin >> n;
vector<in> pt(n+1);
vector<int> w(n+1);
for(int i = 1; i <= n; i++)
cin >> pt[i][0] >> pt[i][1] >> w[i];
if(n == 1)
{
cout << max(w[1], 0ll) << "\n";
return 0;
}
vector<array<int, 4>> GG;
for(int i = 1; i <= n; i++)
{
for(int j = i+1; j <= n; j++)
{
auto [x, y] = sloppy(pt[i], pt[j]);
GG.pb({x, y, i, j});
}
}
sort(GG.begin(), GG.end(), comp);
//murder();
vector<vector<in>> ff;
in lst = {-1, -1};
for(auto [x, y, i, j]: GG)
{
//cout << x << " " << y << endl;
if(((in){x, y}) == lst)
ff.back().pb({i, j});
else
{
ff.pb({{i, j}});
lst = {x, y};
}
}
/*for(auto s: ff)
{
cout << "Next set: " << endl;
for(auto [i, j]: s)
cout << pt[i][0] << " " << pt[i][1] << " " << pt[j][0] << " " << pt[j][1] << endl;
}*/
//murder();
vector<int> where(n+1);
vector<array<int, 3>> srt(n+1);
for(int i = 1; i <= n; i++)
srt[i] = {-pt[i][0], -pt[i][1], i};
sort(srt.begin()+1, srt.end());
vector<int> s(n+1);
for(int i = 1; i <= n; i++)
{
s[i] = w[srt[i][2]];
where[srt[i][2]] = i;
}
seg_tree work;
work.init(n, s);
int ANS = work.Q(1, n, 1, 1, n).S;
//cout << st[0] << " " << st[1] << endl;
for(auto T: ff)
{
/*cout << "Current perm " << endl;
vector<int> WTF(n+1);
for(int i = 1; i <= n; i++)
WTF[where[i]] = i;
for(int i = 1; i <= n; i++)
cout << WTF[i] << " ";
cout << endl;*/
stuff.clear();
Tt.clear();
Spl.clear();
MOON.clear();
for(auto [i, j]: T)
pa[i] = pa[j] = -1;
for(auto [i, j]: T)
{
if(!active[i])
{
stuff.pb(i);
active[i] = 1;
}
if(!active[j])
{
stuff.pb(j);
active[j] = 1;
}
MERGE(i, j);
}
for(auto [i, j]: T)
active[i] = active[j] = 0;
for(auto x: stuff)
{
int y = leader(x);
cmp[y].pb({where[x], x});
if(cmp[y].size() == 1)
Spl.pb(y);
}
for(auto x: Spl)
{
sort(cmp[x].begin(), cmp[x].end());
for(int i = 0; (2*i) < (cmp[x].size()-1); i++)
Tt.pb({cmp[x][i][1], cmp[x][cmp[x].size()-1-i][1]});
MOON.pb({cmp[x][0][0], cmp[x][cmp[x].size()-1][0]});
cmp[x].clear();
}
for(auto [i, j]: Tt)
{
//cout << "Swapping i, j = " << i << ", " << j << endl;
work.upd(where[i], w[j], 1, 1, n);
work.upd(where[j], w[i], 1, 1, n);
swap(where[i], where[j]);
//assert(abs(where[i]-where[j]) == 1);
}
ndata curr = create(0);
int lst = 1;
sort(MOON.begin(), MOON.end());
for(auto [l, r]: MOON)
{
if(l > lst)
curr = merge(curr, work.Q(lst, l-1, 1, 1, n));
curr = merge(curr, create(work.Q(l, r, 1, 1, n).T));
lst = r+1;
}
if(n >= lst)
curr = merge(curr, work.Q(lst, n, 1, 1, n));
ANS = max(ANS, curr.S);
}
cout << ANS << "\n";
return 0;
}
