Областная олимпиада по информатике 2022 года за 11 класс | Казахстанские олимпиады

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

В HS учатся $n$ студентов включая Руслана. Для удобства пронумеруем всех студентов целыми числами от $1$ до $n$, а у Руслана всегда номер $1$.

Известно, что среди студентов есть ровно $m$ пар друзей $(a_1,b_1), …, (a_m,b_m)$. Пара $(a_i,b_i)$ означает что студенты под номерами $a_i$ и $b_i$ являются друзьями.

Недавно Руслан открыл свой кружок по спортивному программированию. Теперь ему нужно пригласить туда как можно больше студентов. По вполне логичным причинам, Руслан сперва начнет приглашать своих друзей. Затем его друзья смогут пригласить своих друзей, а они — своих друзей и так далее.

Однако не все так просто! У каждого студента в HS есть свой навык убеждения $c_i$. Также определим навык убеждения кружка как сумму навыков убеждений каждого отдельного члена кружка. Изначально навык убеждения кружка равен навыку убеждения Руслана: значению $c_1$. Нового студента можно пригласить в кружок только тогда, когда навык убеждения кружка не меньше навыка убеждения этого студента.

Более формально, в любой момент времени любой участник кружка может позвать в кружок своего друга, при условии что сумма навыков убеждений всех членов кружка не меньше навыка убеждения этого друга. Разрешено набирать в кружок новых студентов до тех пор, пока это возможно.

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

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

В первой строке входного файла даны два целых числа $n$ и $m$ — количество студентов в HS и количество пар друзей $(2 \leq n \leq 2 * 10^5, 0 \leq m \leq 2 * 10^5)$.

В следующих $m$ строках содержатся пары $(a_i,b_i)$, обозначающие пары друзей среди студентов. $(1 \leq a_i,b_i \leq n, a_i \neq b_i)$

В последней строке содержатся $n$ целых чисел $c_1,…,c_n$ — навыки убеждения каждого из студентов. $(1 \leq c_i \leq 10^9)$

Гарантируется, что никакая пара студентов не встречается в списке друзей дважды.

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

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

Примеры

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

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

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

4