H. Huge Oil Platform
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Jeroen is planning to build an oil platform in the North Sea. He has found $$$n$$$ $$$(n \leq 400)$$$ locations, where oil can be extracted.

For each place, he has estimated the profit he would get if the oil platform could extract this oil. Because of the hugeness of the oil platform, the oil locations can be seen as points in the plane.

For the purposes of this problem, the earth can be considered flat.

Because of regulations, an oil rig has to be in the shape of a rectangle. Further regulations also make your life difficult. The oil rig itself is quite cheap, but the security fences around the outside of the oil rig are very expensive. This means the cost of building an oil rig is equal to the perimeter of this rectangle. All the locations inside or on the border of the oil platform can be extracted from. It is allowed to build degenerate oil platforms, where the width and/or the height are $$$0$$$.

What is the maximum possible profit Jeroen can get (that is the profits from the oil extraction minus the cost of building the oil platform)? Your answer is considered correct if its absolute or relative error is less than $$$10^{-6}$$$.

Input

The first line of input contains a single integer, $$$n$$$ ($$$1 \leq n \leq 400$$$)  — the number of candidate locations.

Each of the next $$$n$$$ lines contains the description of a candidate drilling location. Each line contains three integers $$$x$$$, $$$y$$$ and $$$w$$$, ($$$0 \leq x,y \leq 10^6,\: 1 \leq w \leq 10^9$$$)  — the coordinates of the point and the profit that can be made drilling at this location.

It is guaranteed that the candidate locations are all distinct.

Output

Print the maximum profit obtainable with a rectangular oil rig. The result should have a relative or absolute error of at most $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$$$$\frac{|a-b|}{\max(1,|b|)} \leq 10^{-6}$$$$$$

Examples
Input
2
1 1 1
3 3 1
Output
1
Input
3
4 5 5
4 6 7
1 3 8
Output
10.1005050633883
Input
2
0 0 1
1000000 1000000 1000000000
Output
1000000000