UTD20s13

#### Start

2020-07-11 09:00 AKDT

## UTD20s13

#### End

2020-07-11 12:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -77 days 23:31:09

3:00:00

0:00:00

# Problem CTrimming 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$.

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.

Sample Input 1 Sample Output 1
4
0 0 1
4 0 3
6 6 100
0 5 4

120

Sample Input 2 Sample Output 2
3
0 0 5
1 0 6
0 1 7

18