Problem E
Trimming Convex Polygons

You are the proud owner of a beautiful convex polygon! But university is expensive, so you decide to sell your polygon to support your studies. The market value, in dollars, for a polygon is exactly twice its area. But there is an illegal black market for individual vertices.

In this problem, you are given a convex polygon with vertices $P$. Each vertex $p_ i \in P$ has a value $v_ i$. You can form a new polygon using a subset of points $Q \subseteq P$. You can then legally sell the polygon formed by vertices $Q$ and also sell the points $P-Q$ on the black market. The amount of money you would earn this way is $2 \cdot {\rm area}(Q) + \sum _{p_ i \in P-Q} v_ i$ where ${\rm area}(Q)$ is the area of the unique convex polygon having vertices $Q$.

Figure 1: Left: Illustration of first sample input. Right: Solution for the first sample. Discard just the point at $(6, 6)$.

You are guaranteed no three vertices of $P$ are collinear, and you also have ${\rm area}(Q) = 0$ for each set $Q$ with at most two points. Note that it is valid for the polygon from $Q$ to be degenerate (i.e. have an area of $0$).

Input

The first line of input consists of a single integer $3 \leq n \leq 200$ indicating the number of points on your convex polygon.

Then $n$ lines follow. The $i$’th such line contains three integers $x_ i, y_ i, v_ i$ describing the coordinates $(x_ i, y_ i)$ and value $v_ i$ of the $i$’ vertex on the polygon. You are guaranteed $|x_ i|, |y_ i| \leq 10^6$ and $0\leq v_ i\leq 10^9$.

The points are given in counterclockwise order around $P$. You are guaranteed no three points are collinear, and the polygon $P$ is convex.

Output

A single line with a single integer indicating the maximum amount of money that can be obtained by selling a subset of $P$ on the black market and legally selling the polygon defined by the remaining points.

4
0 0 1
4 0 3
6 6 100
0 5 4

120

3
0 0 5
1 0 6
0 1 7

18