Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Liên đoàn bóng đá XYZ có n đội bóng đá thành viên, các đội bóng được đánh số từ 1 đến n. Liên đoàn dự định tổ chức các trận đấu giao hữu chuẩn bị cho mùa giải mới. Kế hoạch tổ chức như sau:

·        Liên đoàn sẽ mời một số đội bóng và tổ chức các trận đấu trong k ngày;

·        Trong mỗi ngày, các đội được mời sẽ được chia thành các cặp để thi đấu giao hữu, mỗi đội đá đúng một trận;

·        Trong k ngày, không có hai đội nào thi đấu với nhau quá 1 trận.

Qua khảo sát, Liên đoàn biết đội bóng thứ i có độ hâm mộ là p_i và một số cặp đội bóng kỵ dơ nhau. Do đó, Liên đoàn quyết định danh sách các đội được mời để thực hiện kế hoạch đề ra phải thỏa mãn thêm điều kiện: trong số các đội được mời không có hai đội nào kỵ giơ nhau, và hơn nữa tổng độ hâm mộ của các đội được mời là lớn nhất.

Yêu cầu: Cho hai số nguyên dương n, k, độ hâm mộ của n đội bóng p₁, p₂, …, p_n và mối quan hệ kỵ dơ giữa các đội, hãy xây dựng một kế hoạch thi đấu thỏa mãn điều kiện đã nêu.

Input

Dòng đầu tiên ghi số nguyên dương T (T ≤ 10) là số lượng test. Tiếp đến là T nhóm dòng, mỗi nhóm dòng là dữ liệu của một test theo khuôn dạng:

·        Dòng đầu của nhóm chứa ba số nguyên dương n, m, k;

·        Dòng thứ hai chứa n số nguyên dương p₁, p₂, ..., p_n (p_i  £ 10⁶, i = 1, 2, ..., n);

·        Tiếp theo là m dòng, mỗi dòng chứa 2 số nguyên dương i, j cho biết hai đội bóng i và j là kỵ giơ nhau.

Giả thiết là n ≤ 500 và có không quá 20 đội kỵ giơ với nhiều hơn 2 đội bóng khác. Hai số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra thiết bị ra chuẩn gồm T dòng tương ứng với T test trong dữ liệu vào, mỗi dòng ghi tổng độ hâm mộ của các đội được mời lớn nhất. Nếu với bộ dữ liệu đã cho không tồn tại kế hoạch thi đấu thỏa mãn điều kiện đề bài thì ghi số −1.

Example

Input:
1
5 1 2 
5 2 1 1 1
1 2


Output:
8