Optimal High-speed Train Ring

In a country with uneven terrain, railways are built with different optimal running speeds. Each train route in this country consists of exactly K train segments. For example, when K=5, a route may be represented as T120-D135-S1-G12-K856 where each segment is denoted by a letter prefix followed immediately by a number representing its running speed.

Two routes can be connected if the last train segment of one route is identical to the first train segment of another route. By connecting several routes it is possible to form a cycle. For instance, given three routes:

x1-x2-x3
x3-x4
x4-x5-x1

Assume the speeds corresponding to train segments x1 through x5 are \(v_1, v_2, v_3, v_4, v_5\) respectively. The value of a high-speed rail loop is defined as the average of the speed sums of the routes involved in the cycle. In the above cycle, the three routes have speed sums:

(v_1+v_2+v_3), (v_3+v_4), and (v_4+v_5+v_1) respectively. Hence, the loop value is given by:

[ \frac{(v_1+v_2+v_3)+(v_3+v_4)+(v_4+v_5+v_1)}{3} ]

Given M train routes (each consisting of K segments), your task is to compute the maximum cycle mean, defined as the maximum among the values of all possible high-speed rail rings. Note that each route is used as a whole, and when connecting routes, the entire speed sum of each route is considered. This problem is equivalent to finding a cycle in a weighted directed graph (where each edge corresponds to a route) with the maximum mean weight.

inputFormat

The first line contains an integer M representing the number of routes.

Each of the next M lines contains a string representing a train route. A route is given in the format:

X1-X2-...-XK

where each Xi represents a train segment. Each segment is composed of a letter part (which can be ignored for calculation) and a number part representing the speed. For example, in the segment T120, the speed is 120.

You can assume that K (the number of segments per route) is the same for every route.

outputFormat

Output a single line containing the maximum cycle mean value. The answer will be accepted if it is correct within an absolute or relative error of 1e-6.

sample

3
x1-x2-x3
x3-x4
x4-x5-x1

7.666666667