James là một điệp viên đang nằm vùng tại cơ sở Drhead. Tại đây có n căn phòng bí mật đánh số thứ tự 1,2,…,n. Để vào phòng thứ i cần có chìa khóa phòng đó hoặc phá cánh cửa với chi phí là ~c_i~. Đồng thời, khi thiết kế các căn phòng, người ta tạo ra rất nhiều chìa khóa giấu tại một số phòng khác. James đã có được m thông tin về việc giấu chìa khóa. Thông tin thứ i gồm hai số nguyên dương ~u_i~ và ~v_i~ xác định có một chìa khóa mở phòng ~v_i~ được giấu trong phòng ~u_i~. Một lần James được giao nhiệm vụ cần lấy đủ k tập tài liệu, tài liệu thứ i được đặt ở phòng ~p_i (1≤p_i≤n ∀i∈[1,k])~.

Yêu cầu: Hãy xác định số tiền nhỏ nhất phải bỏ ra để James có thể lấy đủ k tập tài liệu.

Dữ liệu:

• Dòng đầu tiên chứa 3 số nguyên dương ~n,k,m (n≤10^5;m≤2.10^5;k≤12);~
• Dòng thứ hai chứa k số nguyên dương ~p_1,p_2,…,p_k (p_i≤n ∀i∈[1,k]);~
• Dòng thứ ba chứa n số nguyên dương ~c_1,c_2,…,c_n (c_i≤10^6 ∀i∈[1,n]);~
• m dòng tiếp theo, dòng thứ i chứa hai số nguyên dương ~u_i,v_i~ xác định một chìa khóa mở phòng ~v_i~ được giấu trong phòng ~u_i (1≤u_i,v_i≤n)~.

Kết quả: in ra một số nguyên dương duy nhất là số tiền ít nhất mà James phải bỏ ra để lấy đủ k tập tài liệu.

Ví dụ:

Input 1

3 2 1
1 3
7 4 8
2 3

Output 1

11

Input 2

3 2 2
1 3
7 4 8
2 3
1 2

Output 2

7

Giải thích:

• Trong cả 2 ví dụ, cần vào phòng 1 lấy tài liệu số 1, cần vào phòng 3 lấy tài liệu số 2.
• Trong ví dụ 1: Cần phá cửa phòng 1 và phòng 2, sau đó lấy chìa khóa mở phòng 3.
• Trong ví dụ 2: Cần phá cửa phòng 1 lấy chìa khóa mở phòng 2, vào phòng 2 lấy chìa khóa mở phòng 3.

Giới hạn:

• Subtask 1: Có 20% số test m=0;n≤15;
• Subtask 2: Có 20% số test khác n≤15,m≤50;
• Subtask 3: Có 30% số test khác m,n≤2000;
• Subtask 4: Có 30% số test còn lại không có ràng buộc bổ sung;