N points are given on a plane.Each point is having some weight wi.Divide plane in two parts using a line such that weight of part with smaller weight be as maximum as possible.
Weight of part is defined as sum of weight of all the points in that part.
Its given that no three point lies in same line.
First line of input contains N (number of points in the plane)
Each of next N lines contain three integers xi,yi and wi.(xi and yi specifies coordinates of the point and wi specifies weight of the point)
Input is terminated by EOF.
Output an integer specifying maximum possible weight that can be obtained.
0<= |xi|,|yi| <=10^9
0 0 1
0 2 2
2 0 3
2 2 4
When divided by a line,
Coordinates (0,0) & (2,0) are in same part(weight,1+3=4)
Coordinates (0,2) & (2,2) are in same part(weight,2+4=6)
Problem Setter: Abhishek Sanghai