Задача Decentralization. Реформа децентралізації добре вплинула на кількість грошей, які місцева влада може віддати на важливі проекти. Однак не усі міста користуються популярністю серед туристів, а влада прагне якомога збільшити привабливість країни загалом, тому відмітила з усіх N міст рівно K найпопулярніших. Державні експерти порекомендували усім міським головам у разі необхідності “поділитися” їх місцевими бюджетами з іншими містами(*), аби ті могли розвинути туристичний сектор, а також поставили чітку метрику привабливості країни - мінімальний серед бюджетів, виділених на розвиток популярних міст.
Вас же просять допомогти з визначенням максимального показника цієї метрики цього року, з урахуванням поточних запланованих бюджетів.
Примітки
*) за новими антикорупційними правилами, частина бюджету може перейти з одного міста в інше лише у випадку, коли хоча б одне з них туристично популярне (тобто є у тому самому списку з К міст), а крім того між цими двома містами укладено договір співпраці. При цьому ліміту на “переливання” коштів немає (окрім того, що бюджет не має “піти в мінус”). Крім того, дозволяється ділитися лише цілою кількістю гривень.
Технічні умови Програма Decentralization читає з першого рядка стандартного пристрою введення три числа - N та K (1 ≤ K ≤ N ≤ 10’000), а також кількість договорів співпраці M (0 ≤ M ≤ N * (N - 1) / 2). З другого рядка слід прочитати рівно K різних чисел, кожне з яких у межах від 1 до N - відмічені міста. Далі, з третього рядка, програма читає ще N чисел - бюджети міст, кожне число від 0 до 106, i-те число задає бюджет i-го міста. Далі слідують рівно M пар чисел, які задають договори співпраці у форматі Ai Bi, що означає, що між містами Ai та Bi укладено договір.
Програма виводить єдине число - максимальну досяжну метрику, тобто найбільше можливе значення мінімального бюджету серед “популярних” міст після необхідних переливань.
Приклади
|
Введення |
Виведення |
Пояснення |
|
3 2 2 1 3 3 3 3 1 2 2 3
|
4 |
З другого міста можна віддати по 1 гривні у перше та третє місто, після чого їх бюджети будуть рівними - по 4 гривні. При цьому, навіть якщо останню гривню бюджету другого міста віддати якомусь іншому, збільшити метрику не вдасться - адже мінімальний з бюджетів однак буде рівний 4. |
|
3 2 2 2 3 6 0 4 1 2 2 3 |
5 |
Можна перевести з першого міста у друге усі 6 гривень бюджету, після чого з другого у третє перевести 1 гривню. Після цього мінімальне значення бюджету серед популярних міст стане рівним 5. |