B. Беспилотный автомобиль
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дисклеймер: ситуация, описываемая в задаче, имеет мало отношения к реальному проекту беспилотного автомобиля и является исключительно плодом фантазии авторов соревнования.

Как известно, компания Яндекс с недавних пор занимается разработкой беспилотного автомобиля, в чём некоторые из участников финала соревнования, присутствующие в Москве, имеют шанс убедиться лично. Производство беспилотного автомобиля невозможно без тщательного тестирования на специально оборудованном полигоне. В рамках данной задачи вам будет предложено проверить возможности для перемещения беспилотного автомобиля по полигону, имеющему вид дерева.

Полигон состоит из n площадок, соединённых n - 1 дорогами. Площадки пронумерованы числами от 1 до n, а беспилотный автомобиль исходно находится на 1-й площадке. Цель тестирования состоит в том, чтобы провести за минимальное время автомобиль по маршруту, проходящему по каждой из площадок хотя бы раз, если известно, что автомобиль проезжает одну дорогу за одну минуту, а временем на повороты и развороты можно пренебречь.

Задача осложняется тем, что в рамках данного эксперимента навигация может осуществляться только по специальным радиомаякам. На каждой площадке находится радиомаяк, причём заряда включённого радиомаяка, расположенного на площадке i, хватает ровно на ai минут. Будучи выключенным, радиомаяк не тратит заряд. Изначально все радиомаяки выключены.

Процесс перемещения устроен следующим образом. В один момент времени может быть включён только один радиомаяк. Если в начале минуты автомобиль находится на площадке i, а радиомаяк расположен на площадке j и включён в течение t минут, то автомобиль перемещается по t дорогам в сторону уменьшения расстояния до площадки j. Если автомобиль уже находится на одной площадке с радиомаяком, то ничего не происходит. Каждый радиомаяк можно включать на целое количество минут произвольное количество раз.

Определите, можно ли составить план включения-выключения радиомаяков таким образом, чтобы автомобиль посетил все площадки хотя бы по одному разу, и если да, то найдите минимальное необходимое количество минут для этого. Возвращаться на исходную площадку не требуется.

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

В первой строке находится целое число n (1 ≤ n ≤ 200 000) — количество площадок.

Во второй строке находятся целые числа a1, a2, ..., an (0 ≤ ai ≤ 106), где ai — количество минут, на которое хватает заряда в радиомаяке на площадке i.

В последующих n - 1 строках находятся описания дорог, каждое из которых состоит из двух целых чисел ui и vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — номеров соединяемых площадок.

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

Если требуемое возможно, выведите единственное целое число — минимальное время, необходимое для посещения всех площадок. В противном случае выведите число  - 1.

Примеры
Входные данные
7
0 3 0 2 4 3 3
1 2
1 3
3 4
1 5
5 6
6 7
Выходные данные
9
Входные данные
4
0 1 1 2
1 2
2 3
1 4
Выходные данные
-1
Примечание

В первом тесте из условия подходит, например, следующий маршрут:

  • В течение 2 минут держим включённым радиомаяк на площадке 4, в результате чего машина оказывается на площадке 4, а маяк разряжается;
  • В течение 3 минут держим включённым радиомаяк на площадке 2, в результате чего машина оказывается на площадке 2, а маяк разряжается;
  • В течение 2 минут держим включённым радиомаяк на площадке 5, в результате чего машина оказывается на площадке 5, а у маяка остаётся 2 минуты заряда;
  • В течение 2 минут держим включённым радиомаяк на площадке 7, в результате чего машина оказывается на площадке 7, а у маяка остаётся 1 минута заряда.

Таким образом за 9 минут можно посетить все площадки.