Архив Зеленоградского турнира

Во время разработки теории анализа помех в цифровых схемах, перед исследователями возникла следующая проблема. После проведенных эксперементов выяснилось, что часть узлов не может переключаться одновременно. Например известно, что если узел N переключается из состояния 0 в состояние 1, то узел K в данный момент переключится не может в силу логических ограничений в схеме. Каждый узел переключаясь вносит некоторую помеху и эту помеху удалось количественно померить. Исследователям понадобилось придумать способ быстро измерить максимальную помеху, которую могут вызвать переключающиеся узлы. Ученым удалось формализовать задачу следующим образом: Дан граф G = (V, E, w) состоящий из набора вершин V, набора ребер , и весовой функции W, такой что и . Для и , N(u) и N(K) означают соседний набор вершин u и K соответсвенно, формально определенные так:

Набор вершин удовлетворяющий равенству называется независимым. В данной задаче необходимо найти такой набор независимых вершин B что w(B) = max{w(S)}, где S принадлежит множеству всех независимых наборов вершин графа G. Известно также, что плотность ребер в графе находится между 20 и 90%.

Входные данные

t – число тестов [t <= 60]
n k – [n – число вершин (2 <= n <= 250), k – число ребер (1 <= k <= n*(n-1)/2)]
затем через пробел следуют n целых чисел (wi - вес i-ой вершины) [ 0 <= wi <= 2^31-1]
затем следуют k пар целых чисел задающих ребро между вершинами (si sj ребро между i-ой и j-ой вершинами) [1 <= si, sj <= n]. Известно также, что сумма весов всех вершин графа не превышает 10^9.

Выходные данные

Для каждого теста выведите на отдельной строчке MaxWeight – вес максимального независимого набора вершин для данного графа [ 0 <= MaxWeight <= 10^9].

Пример

Входные данные:
2
5 6
10 20 30 40 50
1 2
1 5
2 3
3 4
3 5
4 5

4 4
10 4 10 14
1 2
2 3
3 4
4 1

Выходные данные:
70
20

Иллюстрация к тестам: