B. Вечеринка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В некотором клубе планируется вечеринка, и на нее будут приглашены некоторые из $$$n$$$ участников этого клуба. Все $$$n$$$ участников пронумерованы числами $$$1, 2, \dots, n$$$. Если $$$i$$$-й участник не будет приглашен, уровень уныния на вечеринке увеличится на $$$a_i$$$.

Среди $$$n$$$ участников клуба $$$m$$$ пар друзей. Если оба человека из пары друзей будут приглашены на вечеринку, по традиции они должны будут съесть тортик на двоих. Таким образом, на вечеринке будет съедено ровно столько тортиков, сколько будет пар друзей, в которых оба участника приглашены.

Для вечеринки клуб закажет несколько пар тортиков. Поэтому необходимо, чтобы на вечеринке было съедено четное число тортиков.

Чему равен минимальный возможный уровень уныния на вечеринке, если пригласить участников так, что будет съедено четное число тортиков?

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq \min(10^5,\frac{n(n-1)}{2})$$$) — количество участников в клубе и количество пар друзей.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2, \dots,a_n$$$ ($$$0 \leq a_i \leq 10^4$$$) — значения увеличения уныния.

Каждая из следующих $$$m$$$ строк содержит два целых числа $$$x$$$ и $$$y$$$ ($$$1 \leq x,y \leq n$$$, $$$x \neq y$$$), означающие, что $$$x$$$ и $$$y$$$ друзья. Каждая неупорядоченная пара $$$(x,y)$$$ встречается в каждом наборе входных данных максимум один раз.

Гарантируется, что сумма значений $$$n$$$ и сумма значений $$$m$$$ по всем наборам входных данных не превосходят $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число: минимальное возможное значение уныния.

Пример
Входные данные
4
1 0
1
3 1
2 1 3
1 3
5 5
1 2 3 4 5
1 2
1 3
1 4
1 5
2 3
5 5
1 1 1 1 1
1 2
2 3
3 4
4 5
5 1
Выходные данные
0
2
3
2
Примечание

В первом наборе входных данных можно пригласить всех участников. Уровень уныния будет равен $$$0$$$.

Во втором наборе возможны следующие варианты:

  • пригласить участников $$$1$$$ и $$$2$$$ — $$$0$$$ тортиков, уныние $$$3$$$;
  • пригласить участников $$$2$$$ и $$$3$$$ — $$$0$$$ тортиков, уныние $$$2$$$;
  • пригласить только участника $$$1$$$ — $$$0$$$ тортиков, уныние $$$4$$$;
  • пригласить только участника $$$2$$$ — $$$0$$$ тортиков, уныние $$$5$$$;
  • пригласить только участника $$$3$$$ — $$$0$$$ тортиков, уныние $$$3$$$;
  • не пригласить никого — $$$0$$$ тортиков, уныние $$$6$$$.

Минимальное значение уныния достигается при приглашении участников $$$2$$$ и $$$3$$$.

В третьем примере приглашение участников $$$3,4,5$$$ дает подходящую вечеринку с минимальным возможным значением уныния.