Yuki is a thrifty girl and she always tries her best to economize on money.
Yuki lives in Guangzhou, a metropolis in southern China. Everyday she needs to take the 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 taking metro \(2k\) times (\(k\) times from \(S\) to \(T\) and \(k\) times from \(T\) to \(S\), the first journey must be started at \(S\)).
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 is 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.
Now Yuki taps Yangcheng Tong to take the metro and she wants to know the minimum fares for her to pay every month.