Vấn đề này sử dụng pretest. Tỉ lệ trong subtask áp dụng cho pretest.

Cho một đồ thị đơn, vô hướng có \(n\) đỉnh, \(m\) cạnh. Mỗi đỉnh \(v\) được gán một trọng số dương kí hiệu bởi \(w(v)\). Bạn được thực hiện hai thao tác sau bao nhiêu lần tùy ý:

• Nối hai đỉnh \(u\) và \(v\) bởi một cạnh, chi phí là \(w(u) + w(v)\).
• Cắt cạnh nối hai đỉnh \(u\) và \(v\), chi phí là \(w(u) + w(v)\).

Bạn hãy tính toán chi phí ít nhất để đồ thị sau các thao tác thỏa mãn hai điều kiện:

• Giữa hai đỉnh bất kì của đồ thị có không quá một đường đi.
• Đồ thị không có quá \(k\) thành phần liên thông.

Ghi chú:

• Đồ thị đơn là đồ thị không có khuyên (cạnh nối một đỉnh của đồ thị với chính đỉnh đó), và giữa hai đỉnh chỉ được nối bởi duy nhất một cạnh.
• Thành phần liên thông là các tập đỉnh lớn nhất của đồ thị với tính chất giữa hai đỉnh bất kì trong tập đều có ít nhất một đường đi.

Đầu vào

Dòng đầu tiên chứa ba số nguyên dương \(n, m, k\) \((1 \le m, n, k \le 2*10^5)\).

Dòng tiếp theo chứa \(n\) số nguyên trong khoảng \([1, 10^9]\), số thứ \(i\) \((1 \le i \le n)\) là trọng số được gán cho đỉnh \(i\).

\(m\) dòng tiếp theo, mỗi dòng gồm hai số nguyên trong khoảng \([1, n]\) biểu diễn một cạnh nối hai đỉnh đồ thị.

Ghi chú: Dữ liệu nhập vào đảm bảo đồ thị đơn.

Đầu ra

Một số tự nhiên duy nhất là kết quả bài toán.

Ghi chú: Bạn hãy sử dụng kiểu số nguyên \(64\)bit để xuất dữ liệu.

Subtask

\(25\%\) số test có \(w(v) = 1\) với mọi \(v\) là đỉnh của đồ thị.

\(25\%\) số test có \(k = 1\).

Ví dụ

Đầu vào:

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

Đầu ra:

12

Giải thích: Cắt cạnh \((35)\) tốn chi phí là \(3 + 5 = 8\), nối đỉnh \(1\) và \(3\) tốn chi phí là \(1 + 3 = 4\). Tổng cộng chi phí tối thiểu là \(12\).