Республиканская олимпиада по информатике 2017 год, Павлодар

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

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

В стране Timart есть $N$ городов и $M$ двусторонних дорог. Города пронумерованы от $1$ до $N$. Известно, что с каждого города можно добраться до любого другого по существующим дорогам. Андрей спрятал свитки с секретными алгоритмами в городах Timart. В $i$-ом городе хранится $A_i$ свитков. Рамазан хочет украсть эти свитки. Он может украсть все свитки из города, в котором он находится. Рамазан может начать воровать с любого города. Чтобы не быть пойманным, он не будет использовать одну дорогу два раза подряд. Свитки каждого города можно украсть не более одного раза, посещать города можно по несколько раз. Помогите Рамазану украсть как можно больше свитков.

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

В первой строке входных данных содержится два целых числа $N$, $M$ ($1 \le N \le 5 \cdot 10^5$, $0 \le M \le 5 \cdot 10^5$). Во второй строке находятся $N$ целых чисел $A_1, A_2, \ldots, A_N$, где $A_i$ — количество свитков в $i$-ом городе. В следующих $M$ строках содержится по $2$ целых положительных числа, разделенных пробелом, $u_i$, $v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$)— дорога соединяющая города $u_i$ и $v_i$. Известно, что между двумя городами не может быть больше одной дороги, и что никакая дорога не соединяет город с самим собой. Гарантируется, что между любыми двумя городами существует путь состоящий из заданных дорог

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

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

Система оценки

Данная задача содержит пять подзадач:

1. $1 \le N \le 100$,$M = \frac{N \cdot (N - 1)}{2}$, $1 \le A_i \le 300$, для всех $1 \le i \le N$. Оценивается в $7$ баллов.
2. $1 \le N \le 12$, $0 \le M \le 66$, $1 \le A_i \le 300$, для всех $1 \le i \le N$. Оценивается в $12$ баллов.
3. $1 \le N \le 10^5$, $M = N - 1$, $1 \le A_i \le 10^9$, для всех $1 \le i \le N$. Оценивается в $12$ баллов.
4. $3 \le N \le 10^5$, $M = N$, $1 \le A_i \le 10^9$, для всех $1 \le i \le N$. Оценивается в $25$ баллов.
5. $1 \le N \le 5 \cdot 10^5$, $0 \le M \le 5 \cdot 10^5$, $1 \le A_i \le 10^9$, для всех $1 \le i \le N$. Оценивается в $44$ балла.

Пример:

Вход

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

( Temirlan Satylkhanov )