You have found a collection of floating orbs of light, some of which are nice to look at, and some of which hurt to look at. We model this by each orb having a beauty value which is an arbitrary (possibly negative) integer. We want to build a tent which will house some subset of the orbs, and want the sum of the beauty of the orbs in the tent to be as large as possible. However, the tent must be convex.
Specifically, the position of each orb is at coordinates , where and , and the tent must be a convex polygon that includes the points and . Find the maximum sum of beauty of orbs inside any valid tent configuration.
An orb is considered inside the tent if it is exactly on the tent wall. The tent is considered convex even if some orb is exactly on a straight section of the tent wall (i.e. the angle of the tent wall at that orb is exactly degrees). It is allowed for the tent to not contain any of the orbs (i.e. and just lie on the ground).
The first line of input contains two integers and .
lines of input follow containing three integers each: the and coordinates of an orb and the beauty value of that orb.
Output a line containing a single integer, the maximum sum of beauty of orbs inside any valid tent configuration.
Sample Input 1
10 8 2 7 -1 2 5 2 3 5 1 4 5 -10 6 5 4 6 2 -1 7 2 2 7 3 -1 4 3 3 1 3 1
Sample Output 1