Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Уважаемые участники, убедитесь, что вы прочитали руководство (и особенно раздел «Полезные советы и важные замечания»)!
Рады вновь видеть вас в MMORPG Rawcraft! Наш старый знакомый Вася — зелёный тролль 80-го уровня с большой секирой — тоже всё ещё здесь. Как вы помните, ещё с Волга ИТ — 2014 Вася одержим поиском эпического предмета Золотые Штаны. Сегодня Золотые Штаны появились в одной из локаций, и Васе нужно как можно скорее туда попасть.
Мир Rawcraft содержит N локаций; Вася находится в локации 1, Золотые Штаны — в локации N. Некоторые локации соединены переходами, по которым можно перемещаться в обоих направлениях. Однако войти в переход можно только после того, как локация зачищена от монстров. Изначально в i-й локации находятся Ki монстров.
Вася хочет добраться до Золотых Штанов как можно быстрее. Помогите ему определить минимальное количество монстров, которых придётся уничтожить по пути.
Входные данные
Первая строка содержит целые числа N и M (1 <= N <= 100, 0 <= M <= 10^4) — количества локаций и переходов.
Вторая строка содержит N целых чисел Ki (0 <= Mi <= 100) — количества монстров на каждой локации.
Следующие M строк описывают переходы. Каждая из них содержит целые числа Aj и Bj (1 <= Aj, Bj <= N) — номера локаций, между которыми возможен переход.
Выходные данные
Выведите одно целое число — минимальное количество монстров, которых необходимо уничтожить, чтобы дойти из локации 1 в локацию N. Если Вася не сможет получить Золотые Штаны, выведите -1.
Примеры
| Входные данные | Выходные данные |
4 3
1 2 3 4
1 2
2 3
3 4 | 6 |
4 4
0 10 5 0
1 2
1 3
2 4
3 4 | 5 |
4 2
1 2 3 4
1 2
3 4 | -1 |
Для отправки решений необходимо выполнить вход.
|