Problem C. Cutpoint on the plane ≡

Statement

Doctors of a city polyclinic faced with the problem to find out which combinations of heart rate p_i and systolic blood pressure b_i can lead to bad feeling. To this end, the doctors measured these parameters for n patients and asked them about their feeling. So, they obtained a sample with two features, that is divided into two classes c_i: «1» stands for bad feeling, and «0» denotes feeling well.

The data have been given to the polyclinic information center. Then the problem is to find an optimal separating boundary between classes such that AUC-ROC-metric be as large as possible.

It is required to draw a line through two points from the sample so that when predicting “1” on one side of the line or on the line itself and “0” in other cases, the classification is the best.

AUC is calculated as follows. The number of real ones K₁ and real zeros K₀ which are located on the positive half-plane are calculated. Then AUC = 0.5 + 0.5 ⋅ K₁N₁ − 0.5 ⋅ K₀N₀, where N₁ is the total number of ones, N₀ is the total number of zeros.

It is worth noting that we call positive (corresponding to the class «1») the half-plane for which AUC is greater.

Input format

The first line contains a single integer n. This is followed by n triples of the numbers p_i, b_i, c_i. The numbers p_i, b_i are real, c_i are 0 or 1. It is guaranteed that there is at least one point belonging to class 1 and at least one point belonging to class 0. There are no three points (p_i, b_i) at same line.

Output format

Output a single real number — maximal value of AUC metric with at least 3 digits after decimal point.

Constraints

2 ≤ n ≤ 1000 0 ≤ p_i, b_i ≤ 10⁹ c_i ∈ 0, 1

Sample tests

4
0.0 0.0 1
1.0 1.0 1
0.0 1.0 0
1.0 0.0 0

0.75

5
1 1 1
0 1 1
1 0 1
0 0 1
3 2 0

1