Problem Description

Translated from JOI Open 2017 T2 「ブルドーザー / Bulldozer」.

There are $N$ points on the plane. Point $i\:(1\le i\le N)$ is located at $(X_i, Y_i)$, and its weight is a non-zero integer $W_i$ (it may be negative).
Draw two parallel lines on the plane. The total value is defined as the sum of the weights of all points lying between the two parallel lines (including points on the lines). Find the maximum possible total value.

Input Format

The first line contains an integer $N$.
In the next $N$ lines, the $i$-th line contains three integers $X_i, Y_i, W_i$ separated by spaces.

Output Format

Output one line containing one integer, representing the maximum total value.

5
-5 5 -2
2 5 10
1 4 -2
4 -5 4
-2 2 7

19

6
0 0 6
1 0 -2
2 0 8
0 1 -2
1 1 5
2 1 -2

15

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

5

2
0 0 -1
1 0 -1

0

Hint

Sample Explanation 1.

Choose points $2, 3, 4, 5$.

Sample Explanation 2.

Note that points $1, 2, 3$ are collinear. Points $4, 5, 6$ are collinear.

Sample Explanation 3.

In this sample, no three points are collinear. One chosen parallel line passes through points $1, 2$, and the other passes through points $3, 4$.

Constraints

All input testdata satisfy the following conditions.

$1\le N\le 2000$, $|X_i|, |Y_i|\le 10^9$, $1\le |W_i|\le 10^9\:(1\le i\le N)$. $(X_i, Y_i)\ne (X_j, Y_j)\:(1\le i<j\le N)$.

Translated by ChatGPT 5