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

Есеп B. Достар

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

1 second

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

256 megabytes

HS-те Русланды қосқанда $n$ студент бар. Ыңғайлы болу үшін барлық студенттерді $1$-дан $n$-ға дейінгі бүтін сандармен нөмірлейік, ал Русланның нөмірі әрқашан $1$ болсын. Студенттер арасында $(a_1, b_1), \ldots, (a_m, b_m)$ деген дәл $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 )