Retos de programación - 018: Fiesta

Estás organizando una fiesta para tus amigos, pero como tus amigos no se conocen todos entre sí, te preocupa que algunos de ellos no disfruten de la fiesta. Para evitarlo, decides invitar también a algunos amigos de tus amigos. Pero, ¿a quién debe invitar para que la fiesta sea fantástica?

Afortunadamente, tienes datos de todas las amistades de tus amigos y sus amigos. En terminología de teoría de grafos, tienes un subconjunto G del gráfico social, cuyos vértices (o nodos) corresponden a tus amigos y sus amigos (excluyendote a ti mismo), y las aristas de este gráfico indican las amistades mutuas. Por otra parte, se ha podido obtener estimaciones exactas de la cantidad de comida que cada persona de G consumirá durante la fiesta si fuera invitada.

Quieres elegir a una serie de invitados de G. Este conjunto de personas debe incluir a todos tus amigos, y el subgrafo de G formado por los invitados debe ser conexo (no debe haber personas que no sean amigos de otras personas que también estén invitadas). Esperas que esto asegure de que todos sus amigos disfrutarán de la fiesta, porque dos cualesquiera tendrán algo de qué hablar...

Con el fin de ahorrar dinero, quieres escoger el conjunto de invitados de modo que la cantidad total de alimentos que se necesita sea la menor posible. Si hubiera varias maneras de conseguirlo, preferirías una con el menor número posible de personas.

Las personas (los nodos en el subconjunto G del grafo social) están numeradas de 0 a N-1. Además, para mayor comodidad, tusamigos están numerados del 0 a F-1, donde F es la cantidad de amigos que quieres invitar. También puede dar por sentado que G es conexo. Ten en cuenta (una vez más) que tú no estarás representado en G.

Entrada

La primera línea de la entrada consta de un solo número T, que es el número de casos de prueba. Cada caso de prueba comienza con una línea que contiene tres enteros: N (el número de nodos en G), F (el número de amigos), y M (el número de aristas en G). A continuación, habrá M líneas, cada uno con dos números enteros. Cada una de estas líneas contiene dos números enteros distintos u y v, que indican una amistad mutua entre la persona u y la persona v. Finalmente, habrá una única línea que contiene N enteros separados por espacios, donde el i-ésimo número que representa la cantidad de comida consumida por persona i.

Salida

T líneas de salida, cada una de ellas con la respuesta a cada caso de prueba en una sola línea. Cada línea debe contener dos números: el primero es la cantidad mínima total de alimentos que se consumen en una fiesta, cumpliendo los criterios especificados; el segundo número es la cantidad mínima de personas que habría en esa fiesta.

Limitaciones

T = 50
1 ≤ F ≤ 11
F ≤ N-1
2 ≤ N ≤ 250
N-1 ≤ M ≤ N * (N - 1) / 2
G es conexo y no contiene bucles ni aristas duplicadas.
Para cada persona, la cantidad de comida que consumiría es un número entero entre 0 y 1000, ambos inclusive.

(Asegúrate de que has leído las preguntas frecuentes antes de plantear tu solución)