Background

Phantom Country has built the most advanced high-speed rail system in the world. Its trains are divided into the following types:

• $S$—high-speed photon-powered train—speed $1000\,km\cdot h^{-1}$
• $G$—high-speed EMU—speed $500\,km\cdot h^{-1}$
• $D$—EMU set—speed $300\,km\cdot h^{-1}$
• $T$—express—speed $200\,km\cdot h^{-1}$
• $K$—fast—speed $150\,km\cdot h^{-1}$

A train service number starts with one of the letters above, followed by a positive integer $(\le 1000)$.

Background

Phantom Country has built the most advanced high-speed rail system in the world. Its trains are divided into the following types:

• $S$—high-speed photon-powered train—speed $1000\,km\cdot h^{-1}$
• $G$—high-speed EMU—speed $500\,km\cdot h^{-1}$
• $D$—EMU set—speed $300\,km\cdot h^{-1}$
• $T$—express—speed $200\,km\cdot h^{-1}$
• $K$—fast—speed $150\,km\cdot h^{-1}$

A train service number starts with one of the letters above, followed by a positive integer $(\le 1000)$.

Problem Description

Because the terrain of the country is uneven, the suitable operating speed of railways differs from place to place.

Therefore, each travel route in the country consists of $K$ train services.

For example, when $K=5$, one route is: $T120-D135-S1-G12-K856$.

When the last service of one route is the same as the first service of another route, these two routes can be connected into a longer travel route.

Obviously, connecting several routes may form a cycle.

If there are $3$ travel routes as follows:

$x_1-x_2-x_3$
$x_3-x_4$
$x_4-x_5-x_1$

The speeds of services $x_1 \sim x_5$ are $v_1 \sim v_5$, respectively.

Define the value of a high-speed rail cycle as the average of (the sum of speeds on each travel route in the cycle), i.e.:

$\dfrac{(v_1+v_2+v_3)+(v_3+v_4)+(v_4+v_5+v_1)}3$

The maximum value among all high-speed rail cycles is called the value of the optimal high-speed rail cycle.

Given $M$ travel routes, find the value of the optimal high-speed rail cycle.

Input Format

The first line contains the number of travel routes $M$.

The next $M$ lines each contain one travel route, consisting of several train services separated by -. The numbering rule of train services is as described above.

The input is guaranteed to be valid.

Output Format

Output the value of the optimal high-speed rail cycle, rounded to the nearest integer.

If no such cycle exists, output $-1$.

3
T120-D135-S1
S1-G12
G12-K856-T120

1283

Hint

Sample Explanation

$\dfrac{(200+300+1000)+(1000+500)+(500+150+200)}3=1283$

Constraints

For $50\%$ of the testdata, $0<M\le1000$.

For $100\%$ of the testdata, $0<M\le50000$, and the number of train services in each travel route does not exceed $20$.

The input is large. Please use read and scanf. The testdata does not guarantee that using cin will pass within the time limit.

To avoid precision issues, please use double. The testdata guarantees that the result does not exceed $2147483647$.

Translated by ChatGPT 5