You have found a collection of 
~N~ 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 
~(x, y)~, where 
~0 < x < L~ and 
~y > 0~, and the tent
must be a convex polygon that includes the points 
~(0, 0)~ and 
~(L, 0)~. 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 
~180~ degrees). It is allowed for the tent to not contain any of the orbs (i.e. and just lie on the
ground).
Input Specification
The first line of input contains two integers 
~0 < N \le 2000~ and 
~0 < L \le 10^9~.
~N~ lines of input follow containing three integers each: the ~0 < x < L~ and 
~0 < y \le 10^9~ coordinates of an
orb and the beauty value 
~-10^6 \le b \le 10^6~ of that orb.
Output Specification
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
9
Comments
What is a "tent wall"? I presume it means an edge of the convex polygon we are building?
How is whether an orb is on a tent wall even related to the convexity of the tent? In fact, what is even "the angle of the tent wall at the orb"? Angle between wall and what?
Yes
I think it's possible that someone might misinterpret an orb being directly along the tent wall as forcing it to "bulge out" or something similar (which could make the shape no longer convex). I think all it means is that if an orb is along the tent wall, we should still include it in the sum. Indeed, I ignored this note during the contest and it was fine.
The positions of the orbs don't have to be distinct.