Thủy Điện Hòa Bình là thủy điện lớn thứ 2 ở Đông Nam Á, phía sau công trình vĩ đại ấy có một lòng hồ, nơi cung cấp nguồn nước và điều hòa khí hậu cho thành phố Hòa Bình. Lòng hồ Hòa Bình được mệnh danh là "Hạ Long trên cạn" với nhiều quần thể sinh vật phong phú và đa dạng. Đây cũng là một điểm du lịch hấp dẫn mà du khách thường ghé thăm khi đến Hòa Bình.

Vinh là một thương gia, hằng năm anh sẽ thu mua nông sản của những người dân các đảo trên lòng hồ Hòa Bình. Có ~n~ hòn đảo được đánh số từ ~1~ đến ~n~, những người dân trên hòn đảo thứ ~i~ sẽ cung cấp ~c_i~ kg nông sản. Những ngày thường trong tuần, có ~m~ tuyến tàu dân sinh vận chuyển nông sản. Tuyến tàu thứ ~i~ (~1 \le i \le m~) cho phép di chuyển một chiều từ đảo ~u_i~ sang đảo ~v_i~. Đầu tuần, Vinh thuê một tàu dân sinh, xuất phát từ một đảo đi theo các tuyến cho phép để thu mua nông sản và dừng lại tại một đảo. Cuối tuần, Vinh sẽ thuê tàu dịch vụ khác để vận chuyển mang bán. Vinh dự định sẽ mua hàng ở không quá ~k~ đảo.

Yêu cầu: Hãy lập trình tính tổng khối lượng nông sản lớn nhất mà Vinh có thể thu mua được.

Input

• Dòng đầu ghi ba số nguyên dương ~n, m, k~ (~1 \le n, m \le 10^5; 1 \le k \le 30~).
• Dòng thứ hai ghi ~n~ số nguyên ~c_1, c_2, ..., c_n~ (~1 \le c_i \le 10^5, \forall i = 1, 2, ..., n~) là khối lượng nông sản mà người dân cung cấp ở hòn đảo thứ ~i~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ (~1 \le i \le m~) ghi hai số nguyên ~u_i, v_i~ (~1 \le u_i, v_i \le n~) thể hiện tuyến tàu một chiều từ hòn đảo ~u_i~ đến hòn đảo ~v_i~.

Output

• Một số nguyên là tổng khối lượng nông sản lớn nhất mà Vinh có thể thu mua được.

Sample Input 1

7 7 3
10 10 15 10 20 25 30
2 3
5 1
3 4
4 1
4 6
4 7

Sample Output 1

65

Giải thích ví dụ

Tuyến di chuyển của tàu theo thứ tự là ~5 \to 1 \to 3 \to 4 \to 7~. Vinh sẽ chọn mua hết nông sản ở các đảo ~5, 3, 7~.

Subtasks