James là một điệp viên đang làm nhiệm vụ tại cơ sở Drhead. Tại đây có \(n\) căn phòng bí mật được đánh số thứ tự từ \(1, 2, ..., n\). Để vào phòng thứ \(i\), James 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 đã nhận được \(m\) thông tin về vị trí 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 rằng 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 \le p_i \le n, ∀ i ∈ [1, k])\).

Yêu cầu

• Hãy xác định chi phí nhỏ nhất mà James phải bỏ ra để có thể lấy đủ \(k\) tập tài liệu.

Dữ liệu vào

• Dòng đầu chứa \(3\) số nguyên dương \(n, k, m\) \((n \le 10^5, m \le 2 \times 10^5, k \le 12)\);
• Dòng thứ hai chứa \(k\) số nguyên dương \(p_1, p_2, ..., p_k\) \((p_i \le n, ∀ i ∈ [1, k])\);
• Dòng thứ ba chứa \(n\) số nguyên dương \(c_1, c_2, ..., c_n\) \((c_i \le 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 \le u_i, v_i \le n)\).

Dữ liệu ra

• Một số nguyên duy nhất là chi phí ít nhất mà James phải bỏ ra để lấy đủ \(k\) tập tài liệu.

Ràng buộc

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

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\).

Cách thực hiện:

Ví dụ \(1\): Phá cửa phòng \(1\) và phòng \(2\), sau đó lấy chìa khóa mở phòng \(3\).

Ví dụ \(2\): 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\).