Problem Q: Metro

Problem Q: Metro

Time Limit: 2 Sec  Memory Limit: 512 MB
Submit: 18  Solved: 6
[Submit][Status][Web Board]

Description

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.

Input

The first line contains four integers: \(n\), \(m\), \(k\) and \(q\) \((1\leq n\leq 100, 1\leq m\leq 1\ 000, 1\leq k\leq 30, 1\leq q\leq 10)\)--- the number of stations, edges, times needed to go to school and the total number of queries respectively.

Each of the following \(m\) lines contains three integer \(u_i\), \(v_i\) and \(w_i\) \((1\leq u_i,v_i\leq n, 1\leq w_i\leq 20\ 000,u_i\neq v_i)\), meaning that there is a bidirectional edge from \(u_i\) to \(v_i\) with distance \(w_i\). Please be reminded that \(w_i\) is in the unit of meter.

Each of the following \(q\) lines contains two integer \(S_i, T_i\) \((S_i\neq T_i)\) --- a query where \(S=S_i\) and \(T=T_i\). It is guaranteed that \(S_i\) and \(T_i\) are connected.

Output

For each of the queries, print one line with the result --- the minimum cost Yuki needs to pay every month. The result should be accurate to two decimal places.

Sample Input

7 7 30 1
1 2 4000
2 3 4000
3 4 3000
4 5 6000
5 6 2000
1 7 5000
7 6 9000
1 6

Sample Output

201.25

HINT


A tweet may be helpful for you to solve the problem.
You need to think carefully about the departure and arrival of the first 15 journeys.


metro_news

[Submit][Status]