Problem Description

Takahashi Norm's potential is infinite. There are many people named Takahashi Norm in this world.

There are $ N $ Takahashi Norms on a 2D plane. The $ i(1≦i≦N) $th Takahashi Norm is located at coordinates $ (x_i,y_i) $. Each Takahashi Norm is assigned a positive integer constant $ c_i $. It takes $c_i * \max(\|x_i-X\|, \|y_i-Y\|)$ time for the $ i $th Takahashi Norm to move to a point $ (X,Y) $.

Your task is to find the minimum time required for all Takahashi Norms to gather at one point. The minimum time required to gather at one point is defined as the time taken by the slowest Takahashi Norm to arrive at that point.

Takahashi Norms start moving simultaneously and do not interfere with each other.

Input Format

The input is given from the standard input in the following format:

$ N $ $ x_1 $ $ y_1 $ $ c_1 $ $ x_2 $ $ y_2 $ $ c_2 $ : $ x_N $ $ y_N $ $ c_N $

• The first line contains an integer $N\ (2≦N≦1,000)$, representing the number of Takahashi Norms.
• The next $ N $ lines, where the $i\ (1≦i≦N)$th line contains three integers $x_i,y_i,c_i\ (-10^5≦x_i,y_i≦10^5,1≦c_i≦1,000)$, representing the position on the 2D plane and the constant for the $ i $th Takahashi Norm, separated by spaces.
• Multiple Takahashi Norms may be at the same coordinates.

Output Format

Output the minimum time required for all Takahashi Norms to gather at one point. The answer will be considered correct if the absolute or relative error is at most $ 10^{−4} $. End the output with a newline.

Sample Input and Output

Sample Input #1

2
0 0 1
10 10 1

Sample Output #1

5.000000000000000

Sample Input #2

2
0 0 1
10 10 2

Sample Output #2

6.666666666666667

Sample Input #3

10
-27 -67 10
59 13 10
14 -15 9
-29 -84 7
-75 -2 2
-12 -74 5
77 31 9
40 64 8
-81 32 1
81 26 5

Sample Output #3

582.222222222222222

Sample Input #4

8
-81739 73917 446
42230 30484 911
79354 -50126 200
33440 -47087 651
-73 84114 905
79222 -53608 713
65194 -46284 685
81145 40933 47

Sample Output #4

54924095.383189122374461

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $ c_i=1 $ for any $ i(1≦i≦N) $, you will be awarded $ 30 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 70 $ points.

Sample Explanation 1

If the gathering point is set to $ (5,5) $, both Takahashi Norms can move to that point in 5 seconds, which is the minimum time.

见题面 Input 部分

见题面 Output 部分