All Submissions


Problem Statement

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.

Input

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

Output an integer specifying maximum possible weight that can be obtained.

Constraints

N<=100
0<= |xi|,|yi| <=10^9
1<=wi<=10000

Sample Input


4
0 0 1
0 2 2
2 0 3
2 2 4


Sample Output


4


Explanation

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

Languages: C,C++,Java

Time Limit: 2 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0