3-й этап Республиканской олимпиады по информатике 2021-2022, 2 тура

Задача B. Друзья

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

1 секунда

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

256 мегабайт

В HS учатся $n$ студентов включая Руслана. Для удобства пронумеруем всех студентов целыми числами от $1$ до $n$, а у Руслана всегда номер $1$. Известно, что среди студентов есть ровно $m$ пар друзей $(a_1, b_1), \ldots, (a_m, b_m)$. Пара $(a_i, b_i)$ означает что студенты под номерами $a_i$ и $b_i$ являются друзьями. Недавно Руслан открыл свой кружок по спортивному программированию. Теперь ему нужно пригласить туда как можно больше студентов. По вполне логичным причинам, Руслан сперва начнет приглашать своих друзей. Затем его друзья смогут пригласить своих друзей, а они — своих друзей и так далее. Однако не все так просто! У каждого студента в HS есть свой навык убеждения $c_i$. Также определим навык убеждения кружка как сумму навыков убеждений каждого отдельного члена кружка. Изначально навык убеждения кружка равен навыку убеждения Руслана: значению $c_1$. Нового студента можно пригласить в кружок только тогда, когда навык убеждения кружка не меньше навыка убеждения этого студента. Более формально, в любой момент времени любой участник кружка может позвать в кружок своего друга, при условии что сумма навыков убеждений всех членов кружка не меньше навыка убеждения этого друга. Разрешено набирать в кружок новых студентов до тех пор, пока это возможно.

Визуализация первого примера. Синим помечены студенты вступившие в кружок.

Визуализация второго примера. Синим помечены студенты вступившие в кружок.

Какое максимальное количество студентов Руслан сможет набрать к себе в кружок (включая самого Руслана)?

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

В первой строке входного файла даны два целых числа $n$ и $m$ — количество студентов в HS и количество пар друзей ($2 <= n <= 2 \cdot 10^5$, $0 <= m <= 2 \cdot 10^5$). В следующих $m$ строках содержатся пары $(a_i, b_i)$, обозначающие пары друзей среди студентов. ($1 <= a_i, b_i <= n$, $a_i \neq b_i$) В последней строке содержатся $n$ целых чисел $c_1, \ldots, c_n$ — навыки убеждения каждого из студентов. ($1 <= c_i <= 10^9$) Гарантируется, что никакая пара студентов не встречается в списке друзей дважды.

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

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

Примеры:

Вход

7 6
1 2
3 1
1 4
5 3
4 5
6 7
2 2 1 12 5 3 6

Ответ

4

Вход

5 4
1 2
1 3
1 4
1 5
4 18 6 16 4

Ответ

3

Вход

2 0
1 1

Ответ

1

Замечание

Разберем первый пример.

• Изначально Руслан один в секции. Навык убеждения кружка равен $c_1 = 2$. Руслан может пригласить в кружок друзей $2$ и $3$, но не может пригласить друга $4$, поскольку его навык убеждения $c_4 = 12 > 2$.
• Теперь в секции Руслана есть студенты $1$, $2$ и $3$. Навык убеждения кружка равен $c_1 + c_2 + c_3 = 2 + 2 + 1 = 5$. Студент номер $3$ может пригласить своего друга $5$ ($c_5 = 5 <= 5$). По прежнему пригласить студента $4$ не удается ($c_4 = 12 > 5$).
• Теперь в секции Руслана есть студенты $1$, $2$, $3$ и $5$. Навык убеждения кружка равен $c_1 + c_2 + c_3 + c_5 = 2 + 2 + 1 + 5 = 10$. Однако больше никаких студентов позвать в кружок невозможно. Студенты $6$ и $7$ не являются друзьями студентов в секции, а у студента $4$ по прежнему навык убеждения больше ($c_4 = 12 > 10$).

( Temirlan Baibolov )