D. Тестирование дерева
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На уроке информатики Якоб построил модель дерева из шариков и палочек. Модель соответствует некоторому дереву, состоящему из n вершин. На создание i-го шарика Якоб потратил ai минут.

Учительница будет оценивать качество модели по количеству усилий, потраченных Якобом на создание шариков. У неё нет времени рассматривать их все, поэтому она посмотрит только на k первых шариков в порядке DFS-обхода дерева. Оценкой Якоба будет минимальное ai среди k рассмотренных шаров.

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

Порядок DFS-обхода — это последовательность номеров вершин, выписанная рекурсивной процедурой DFS. Будучи вызванной от вершины v, процедура делает следующее:

  1. Напечатать v.
  2. Пройтись по списку соседей вершины v и вызвать процедуру DFS от всех из них по очереди. Не вызывать процедуру DFS от вершины u, если мы пришли в вершину v непосредственно из u.
Входные данные

В первой строке входных данных записаны два положительных целых числа n и k (2 ≤ n ≤ 200 000, 1 ≤ k ≤ n) — количество шариков в составленном Якобом дереве и количество шариков, на которые посмотрит учительница, соответственно.

Во второй строке записаны n целых чисел ai (1 ≤ ai ≤ 1 000 000), i-е из которых соответствует количеству времени, потраченному Якобом на i-ю вершину.

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

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

Выведите одно целое число — максимальную оценку, которую может получить Якоб, если правильно выберет корневую вершину и переупорядочит списки соседей.

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

В первом примере Якоб может назначить корнем вершину 2 и переупорядочить список её соседей следующим образом: 4, 1, 5. В результате этого порядок DFS-обхода станет 2, 4, 1, 3, 5, минимальное значение ai среди первых трёх вершин равняется 3.

Во втором примере любой порядок обхода будет содержать вершину 1 на первом или втором месте, поэтому Якоб не может получить оценку больше чем 1.