For the university students, the first problem they face is how to apply for suitable courses based on their actual situation.

Among the selectable courses, there are $2n$ course sessions arranged over $n$ time slots. In the $i$-th ($1 \le i \le n$) time slot, two sessions of the same course content are held simultaneously at different locations, where the student is pre-assigned to attend the session in classroom $c_i$, and the other session is in classroom $d_i$.

Without submitting any application, students must complete all $n$ pre-assigned course sessions in the order of the time slots. If a student wishes to change the classroom for the $i$-th course session, they must submit an application. If the application is approved, the student can attend the session in classroom $d_i$ during the $i$-th time slot; otherwise, they will still attend the session in classroom $c_i$.

Due to the high demand for changing classrooms, applications are not guaranteed to be approved. Through calculation, the student has discovered that for the $i$-th course session, the probability of the application being approved is a known value $k_i$, and for different course applications, the probabilities of approval are independent of each other.

The school regulations state that all applications can only be submitted once before the start of the semester, and each person can choose to apply for at most $m$ courses. This means the student must decide at once whether to apply to change the classroom for each course, and cannot decide whether to apply for other courses based on the results of some course applications. The student can apply for their most desired $m$ courses, or use fewer than $m$ application opportunities, or even not apply for any courses at all.

Since different courses may be held in different classrooms, the student needs to use the time between classes to travel from one classroom to another.

The university where the student is located has $v$ classrooms and $e$ roads. Each road connects two classrooms and is bidirectional. Due to the different lengths and congestion levels of the roads, the physical exertion required to travel on the roads may vary. After the $i$-th ($1 \le i \le n-1$) course session ends, the student will depart from the classroom where they attended that session and choose the path with the minimum physical exertion to travel to the classroom for the next course session.

Now, knowing which courses the student can apply for to minimize the total expected physical exertion for moving between classrooms, please help them find this minimum value.

Input

The first line contains four integers $n, m, v, e$. $n$ represents the number of time slots in the semester; $m$ represents the maximum number of courses the student can apply to change; $v$ represents the number of classrooms in the university; $e$ represents the number of roads in the university.

The second line contains $n$ integers, where the $i$-th ($1 \le i \le n$) integer $c_i$ is the classroom the student is pre-assigned to for the $i$-th time slot; it is guaranteed that $1 \le c_i \le v$.

The third line contains $n$ integers, where the $i$-th ($1 \le i \le n$) integer $d_i$ is the classroom for the other session of the same course for the $i$-th time slot; it is guaranteed that $1 \le d_i \le v$.

The fourth line contains $n$ real numbers, where the $i$-th ($1 \le i \le n$) real number $k_i$ is the probability that the application to change the classroom for the $i$-th time slot is approved; it is guaranteed that $0 \le k_i \le 1$.

Next, $e$ lines follow, each containing three integers $a_j, b_j, w_j$, representing a bidirectional road connecting classrooms $a_j$ and $b_j$, with a physical exertion cost of $w_j$; it is guaranteed that $1 \le a_j, b_j \le v$, $1 \le w_j \le 100$.

It is guaranteed that $1 \le n \le 2000$, $0 \le m \le 2000$, $1 \le v \le 300$, $0 \le e \le 90000$.

It is guaranteed that through the roads in the school, one can reach any other classroom from any classroom.

It is guaranteed that the input real numbers have at most 3 decimal places.

Output

Output one line containing a single real number, rounded to exactly 2 decimal places, representing the answer. Your output must be exactly the same as the standard output to be considered correct.

The test data guarantees that the absolute difference between the rounded answer and the exact answer is no more than $4 \times 10^{-3}$.

Examples

Input 1

3 2 3 3
2 1 2
1 2 1
0.8 0.2 0.5
1 2 5
1 3 3
2 3 1

Output 1

2.80

Note

All feasible application plans and expected gains are as follows:

Examples 2

See the files classroom/classroom2.in and classroom/classroom2.ans in the contestant directory.

Note

1. There may be multiple bidirectional roads connecting the same two classrooms. It is also possible that a road connects the same classroom at both ends.

2. Please distinguish the meanings of $n, m, v, e$. $n$ is the number of time slots, $m$ is the number of application opportunities.