Yuki lives in Guangzhou, a metropolis in southern China. Everyday she needs to take metro for her study. The metro system map of Guangzhou can be considered as a graph \(G\), where there are totally \(n\) nodes as stations and \(m\) bidirectional edges with given distances linking these stations.
Yuki’s home is located nearby station \(S\) and her school is located nearby station \(T\). Also she needs to go to school \(k\) times every month, that means totally take metro \(2k\) times (\(k\) times from \(S\) to \(T\) and \(k\) times from \(T\) to \(S\), the first journey must be started at \(S\)).
Now Yuki taps Yangcheng Tong to take metro and she wants to know the minimum fares for her to pay every month.
The rules of fares in Guangzhou metro are shown as following:
- A journey shorter than 4 km (inclusive), costs ¥2.
- ¥1 is charged for every 4 km after 4 km, every 6 km after 12 km, and every 8 km after 24 km.
- If the departure and arrival station of the journey are the same, also costs ¥2.
Also Yangcheng Tong offers discounts for rides on the metro. Within each month, a 5% discount is available for the first 15 journeys and a 40% discount for all journeys beyond.