Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT016J - ACM PTIT 2016 J - Giao hữu bó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à pi 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 p1, p2, …, pn 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.

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à pi 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 p1, p2, …, pn 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 p1, p2, ..., pn (pi  £ 106, 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 ij 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

Được gửi lên bởi:Admin
Ngày:2016-04-26
Thời gian chạy:1s-5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.