P10951 Optimal High-Speed Rail Cycle

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)$.

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.

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 the value of the optimal high-speed rail cycle, rounded to the nearest integer. If no such cycle exists, output $-1$.

**Sample Explanation** $\dfrac{(200+300+1000)+(1000+500)+(500+150+200)}3=1283$ **Constraints** For $50\%$ of the testdata, $0