Problem Description

Translated from JOI Open 2017 T2 "Bulldozer"

There are $N$ points on a plane, where point $i$ (for $1 \leq i \leq N$) is located at $(X_i, Y_i)$. Each point $i$ has a weight $W_i$, which is a non-zero integer (it can be negative).

The total value obtained by drawing two parallel lines on the plane is the sum of the weights of all points between the lines (including those on the lines). Determine the maximum total value that can be achieved.

Input Format

The first line contains an integer $N$.
The next $N$ lines each contain three space-separated integers $X_i, Y_i, W_i$.

Output Format

Output a single integer, which is the maximum total value.

Sample Input and Output

Sample Input #1

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

Sample Output #1

19

Sample Input #2

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

Sample Output #2

15

Sample Input #3

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

Sample Output #3

5

Sample Input #4

2
0 0 -1
1 0 -1

Sample Output #4

0

Notes

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 also collinear.

Sample Explanation 3

In this sample, no three points are collinear. The chosen parallel lines pass through points $1, 2$ and points $3, 4$.

Data Range

All input data satisfies the following conditions:

$1 \leq N \leq 2000$, $|X_i|, |Y_i| \leq 10^9$, $1 \leq |W_i| \leq 10^9$ (for $1 \leq i \leq N$). $(X_i, Y_i) \neq (X_j, Y_j)$ (for $1 \leq i < j \leq N$).

见题面 Input 部分

见题面 Output 部分