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

(Құпиялы алгоритмдер)

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

2 seconds

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

256 megabytes

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$ ұпайға бағаланады.

\Example Вход

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 )