C. Cutting Sandwiches
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Womais has constructed a sandwich on the plane. There are $$$n$$$ ingredients, where ingredient $$$i$$$ occupies the line segment from $$$(a_i,h_i)$$$ to $$$(b_i, h_i)$$$.

He now wants to share this sandwich with Dilgod by cutting it into two pieces. To do so, Womais chooses a non-horizontal line $$$\ell$$$ which cuts the plane into two pieces. Dilgod will receive the sandwich consisting of the parts on the left side of the line, and Womais the sandwich consisting of the parts on the right.

For each ingredient $$$i$$$, suppose that the line cuts it at the point $$$(c_i, h_i)$$$ (if the line does not intersect ingredient $$$i$$$, set $$$c_i$$$ to be one of $$$a_i$$$ or $$$b_i$$$, depending on which side of the line ingredient $$$i$$$ is on). Then, the goodness of the cut is defined as $$$\sum_{i=1}^{n} (b_i - c_i)(c_i - a_i)$$$.

Given the ingredient locations, help Womais find the maximum goodness of any line cutting them.

Input

The first line of the input contains an integer $$$n$$$ ($$$1\le n \le 100$$$) – the number of ingredients.

The next $$$n$$$ lines describe the ingredients. The $$$i$$$-th line contains the tuple of integers $$$a_i, b_i, h_i$$$ ($$$1\le a_i \lt b_i \le 10^4$$$, $$$1\le h_i \le 10^4$$$) – the location of the $$$i$$$-th ingredient.

It is guaranteed that no two ingredients intersect: that is, there do not exist $$$i\neq j$$$ such that $$$h_i = h_j$$$ and $$$[a_i,b_i]\cap [a_j,b_j] \neq \varnothing$$$.

Output

Output a single real number representing the maximum goodness of a line cutting the ingredients.

Your answer is considered correct if its absolute error or relative error does not exceed $$$10^{-6}$$$. Namely, if your answer is $$$a$$$ and the jury's answer is $$$b$$$, then your answer is accepted if $$$\frac{|a - b|}{\max(1,|b|)} \le 10^{-6}$$$.

Examples
Input
2
1 5 1
2 6 2
Output
8.000000000000
Input
3
3 5 1
4 7 2
3 5 3
Output
3.250000000000