1. Decentralization

Задача Decentralization. Реформа децентралізації добре вплинула на кількість грошей, які місцева влада може віддати на важливі проекти. Однак не усі міста користуються популярністю серед туристів, а влада прагне якомога збільшити привабливість країни загалом, тому відмітила з усіх N міст рівно K найпопулярніших. Державні експерти порекомендували усім міським головам у разі необхідності “поділитися” їх місцевими бюджетами з іншими містами(*), аби ті могли розвинути туристичний сектор, а також поставили чітку метрику привабливості країни - мінімальний серед бюджетів, виділених на розвиток популярних міст.

Вас же просять допомогти з визначенням максимального показника цієї метрики цього року, з урахуванням поточних запланованих бюджетів.

Примітки

*)    за новими антикорупційними правилами, частина бюджету може перейти з одного міста в інше лише у випадку, коли хоча б одне з них туристично популярне (тобто є у тому самому списку з К міст), а крім того між цими двома містами укладено договір співпраці. При цьому ліміту на “переливання” коштів немає (окрім того, що бюджет не має “піти в мінус”). Крім того, дозволяється ділитися лише цілою кількістю гривень.

Технічні умови  Програма Decentralization читає з першого рядка стандартного пристрою введення три числа - N та K (1 ≤ K ≤ N ≤ 10’000), а також кількість договорів співпраці M (0 ≤ M ≤ N * (N - 1) / 2). З другого рядка слід прочитати рівно K різних чисел, кожне з яких у межах від 1 до N - відмічені міста. Далі, з третього рядка, програма читає ще N чисел - бюджети міст, кожне число від 0 до 10⁶, i-те число задає бюджет i-го міста. Далі слідують рівно M пар чисел, які задають договори співпраці у форматі A_i B_i, що означає, що між містами A_i та B_i  укладено договір.

Програма виводить єдине число - максимальну досяжну метрику, тобто найбільше можливе значення мінімального бюджету серед “популярних” міст після необхідних переливань.

Приклади