Rối loạn ám ảnh cưỡng bức (obssesive – compulsive disorder), gọi tắt là OCD, là một rối loạn tâm lý có tính chất mãn tính. Người bị OCD thường lo lắng không chính đáng, suy nghĩ quá mức, có ý nghĩa ám ảnh và phải thực hiện các hành vi mang tính chất ép buộc để giải tỏa căng thẳng. Dấu hiệu rõ thấy của bệnh nhân mắc phải bệnh này thường có một hay một số hành vi lặp lại một cách vô nghĩa như thường xuyên rửa tay, sắp xếp mọi vật theo đúng trình tự của họ một cách không cần thiết hoặc bị ám ảnh về hình ảnh hay con số nào đó.

Bạn Thanes là một người mắc phải OCD, cậu bị ám ảnh với con số ~W~. Mỗi lần cậu được mẹ nhờ đi mua đồ, cậu sẽ chọn đường đi có độ mệt mỏi là nhỏ nhất trong tất cả các đường đi và độ mệt mỏi của đường đi đó phải bằng ~W~. Độ mệt mỏi của một đường đi được định nghĩa là độ dài của con đường có độ dài lớn nhất trong đường đi đó (biết rằng một đường đi sẽ đi qua một hoặc nhiều con đường khác nhau).

Giả sử khu vực của bạn Thanes sống là một đa đồ thị ~G~, trong đó có ~n~ địa điểm và ~m~ con đường hai chiều. Các địa điểm được đánh số từ ~1~ đến ~n~. Tuy nhiên, vì tính chất công việc của ba bạn Thanes, nên bạn phải đổi nơi ở liên tục, đồng thời cũng có rất nhiều những cửa hàng mà cậu có thể đến. Gọi ~A~ là tập các địa điểm gồm những vị trí nhà ở của Thanes, ~B~ là tập các vị trí của những cửa hàng trong khu vực cậu ở.

Yêu cầu: Để tối thiểu hóa khả năng bạn Thanes trong tình trạng căng thẳng, hãy giúp bạn ~T~ tìm số cặp ~(u, v)~ sao cho đường đi từ ~u~ đến ~v~ là đường đi thoả mãn điều kiện trên ~(u ∈ A; v ∈ B)~. Dữ liệu đưa vào luôn đảm bảo các con trong tập ~A~ không thuộc tập ~B~.

Dữ liệu vào

• Dòng đầu tiên gồm năm số nguyên dương ~n~, ~m~, ~W~, ~n_A~, ~n_B~ (~W \le 10^9~, ~n_A~ là số lượng con của tập ~A~, ~n_B~ là số lượng con của tập ~B~).
• ~m~ dòng tiếp theo mô tả các con đường trong đồ thị ~G~, mỗi dòng gồm ~3~ số nguyên dương ~i, j, c_{ij}~ ~(c_{ij} \le 10^9)~.
• Tiếp theo là một dãy gồm ~n_A~ số nguyên dương ~u_1, u_2, u_3, ..., u_{n_A}~ mô tả tập ~A~.
• Tiếp theo là một dãy gồm ~n_B~ số nguyên dương ~v_1, v_2, v_3, ..., v_{n_B}~ mô tả tập ~B~.

Dữ liệu ra

Gồm một dòng là số lượng ~(u,v)~ có đường đi bắt đầu từ ~u~, kết thúc tại ~v~ thỏa mãn điều kiện đề bài.

Ràng buộc

• Có ~40\%~ số lượng test của bài thỏa mãn: ~n_A = n_B = 1~, ~n \le 10^3~, ~m \le 10^5~.
• Có ~30\%~ số lượng test của bài thỏa mãn: ~n_A, n_B \le 10^2~, ~n \le 10^5~, ~m \le 3 \times 10^5~.
• Có ~30\%~ số lượng test của bài thỏa mãn: ~n \le 10^5~, ~m \le 3 \times 10^5~.

Ví dụ

Input

4 6 2 1 2
1 2 1
1 3 1
1 4 2
2 3 2
3 4 2
2 4 2
2
3 4

Output

1

Giải thích

Hình minh hoạ cho ví dụ ~1~:

Ta có cặp ~(2,4)~ là thoả mãn điều kiện đề bài, không tồn tại đường đi nào từ ~(2,4)~ có độ mệt mỏi nhỏ hơn ~2~ và độ mệt mỏi nhỏ nhất của đường đi từ ~2~ đến ~4~ bằng ~W = 2~

Ta không chọn cặp ~(2,3)~ vì tồn tại đường đi là ~2 \rightarrow 1 \rightarrow 3~ có độ mệt mỏi là ~1~ và không bằng ~W = 2~.