Problem L
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 \mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}(Q)+\sum _{p_i\in P-Q}{v}_i$ where $\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}(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 $\mathrm{a}\mathrm{r}\mathrm{e}\mathrm{a}(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\le n\le 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|\le {10}^6$ and $0\le v_i\le {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