Optimizing Classroom Switching Routes

At the beginning of his college life, Niu Niu is faced with choosing the optimal courses. There are (2n) classes arranged in (n) time slots. In the (i)-th time slot ((1 \le i \le n)), two classes on the same subject are held simultaneously in two different rooms: room (c_i) (where Niu Niu is pre‐assigned) and room (d_i).

Before the semester starts, Niu Niu can submit at most (m) applications to switch a class from room (c_i) to room (d_i). For each class (i) where an application is submitted, the application is approved with probability (k_i) and rejected with probability (1-k_i); all events are independent. If approved, Niu Niu attends the class in (d_i); if not, he remains in (c_i). For classes without an application, he must attend the class in (c_i).

After each class (except the last one), he needs to travel to the next class's room. The university has (v) classrooms connected by (e) bidirectional roads. Each road connects two classrooms and has a given positive cost (representing the expenditure of energy). Between any two classrooms, Niu Niu always takes the route with the minimum total cost.

For each consecutive pair of classes (i) and (i+1) ((1 \le i \le n-1)), the travel cost depends on the room he ends up in after class (i) and the room where he attends class (i+1}. Specifically, if no application is submitted for a course, the classroom is certainly (c_i); if an application is submitted, the classroom is (d_i) with probability (k_i) and (c_i) with probability (1-k_i).

Let (d(u,v)) denote the minimum travel cost between classroom (u) and classroom (v). Then the expected travel cost from class (i) to class (i+1) is defined as follows:

• If no application is submitted for both courses (i) and (i+1): (d(c_i, c_{i+1})).
  
• If an application is submitted only for course (i+1): ((1-k_{i+1}),d(c_i, c_{i+1}) + k_{i+1},d(c_i, d_{i+1})).
  
• If an application is submitted only for course (i): ((1-k_i),d(c_i, c_{i+1}) + k_i,d(d_i, c_{i+1})).
  
• If applications are submitted for both courses: ((1-k_i)(1-k_{i+1}),d(c_i, c_{i+1}) + (1-k_i)k_{i+1},d(c_i, d_{i+1}) + k_i(1-k_{i+1}),d(d_i, c_{i+1}) + k_i k_{i+1},d(d_i, d_{i+1})).
  
  Determine which courses Niu Niu should apply to (no more than (m) in total) so that the expected total travel cost (i.e. the sum over all (n-1) consecutive pairs) is minimized.

inputFormat

The input consists of multiple lines as follows:

• The first line contains four integers (n), (m), (v), and (e) ((1 \le n \le 10^5), (0 \le m \le n); the bounds for (v) and (e) are such that the shortest paths computations can be performed).
  
  
• The second line contains (n) integers (c_1, c_2, \dots, c_n) ((1 \le c_i \le v)), the classrooms where classes are originally held.
  
  
• The third line contains (n) integers (d_1, d_2, \dots, d_n) ((1 \le d_i \le v)), the alternative classrooms for each class.
  
  
• The fourth line contains (n) real numbers (k_1, k_2, \dots, k_n) (each between 0 and 1), where (k_i) is the probability that the application for class (i) is approved.
  
  
• Each of the next (e) lines contains three integers (u), (v), and (w) ((1 \le u,v \le v) and (w > 0)), describing a bidirectional road connecting two classrooms with cost (w>.

outputFormat

Output a single real number, the minimum expected total travel cost. Answers within a relative or absolute error of (10^{-6}) will be accepted.

sample

3 1 3 3
1 2 3
2 3 1
0.5 0.5 0.5
1 2 1
2 3 1
1 3 3

1.5