Республиканская олимпиада по информатике 2017 года за 10 класс | Казахстанские олимпиады

Задача G. Секретные алгоритмы

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

В стране Timart есть NN городов и MM двусторонних дорог. Города пронумерованы от 11 до NN. Известно, что с каждого города можно добраться до любого другого по существующим дорогам. Андрей спрятал свитки с секретными алгоритмами в городах Timart. В ii-ом городе хранится AiA_i свитков. Рамазан хочет украсть эти свитки. Он может украсть все свитки из города, в котором он находится. Рамазан может начать воровать с любого города. Чтобы не быть пойманным, он не будет использовать одну дорогу два раза

Формат входного файла

В первой строке входных данных содержится два целых числа NN, MM (1N51051 \le N \le 5 \cdot 10^5, 0M51050 \le M \le 5 \cdot 10^5). Во второй строке находятся NN целых чисел A1,A2,,ANA_1, A_2, \ldots, A_N, где AiA_i — количество свитков в ii-ом городе. В следующих MM строках содержится по 22 целых положительных числа, разделенных пробелом, uiu_i, viv_i (1ui,viN,uivi1 \le u_i, v_i \le N, u_i \neq v_i)— дорога соединяющая города uiu_i и viv_i. Известно, что между двумя городами не может быть больше одной дороги, и что никакая дорога не соединяет город с самим собой. Гарантируется, что между любыми двумя городами существует путь состоящий из заданных дорог

Формат выходного файла

Выведите одно целое число — максимальное количество свитков, которое может украсть Рамазан.

Примеры

Вход

8 8
1 2 3 4 5 6 7 8
1 2
2 3
2 4
2 5
5 6
6 7
7 8
8 5

Выход

35