Цепная реакция
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Роберт Оппенгеймер любит представлять взаимодействия между ядрами атомов в ядерной реакции в виде деревьев.

Для каждого ядра, используемого Робертом, известно две характеристики: $$$a_i$$$ и $$$b_i$$$ — количество нейтронов и протонов. При взаимодействия ядра $$$i$$$ с ядром $$$j$$$ происходит переход заряда от ядра $$$i$$$ к ядру $$$j$$$. При этом значение заряда изменяется одним из двух способов: увеличивается на $$$a_j - a_i$$$ или увеличивается на $$$b_j - b_i$$$.

Во время очередного эксперимента Оппенгеймер передал заряд, равный $$$1$$$, ядру с номером $$$s$$$. Далее этот заряд распространился по дереву взаимодействий по всем остальным ядрам так, что при каждом взаимодействии двух ядер, заряд изменился одним из двух описанных выше способов.

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

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

В первой строке входных данных даны два числа $$$n$$$ и $$$s$$$ — количество ядер атомов в дереве взаимодействий и номер атома, которому Роберт передал заряд в начале эксперимента ($$$1 \le n \le 10^5$$$; $$$1 \le s \le n$$$).

Во второй строке через пробел дано $$$n$$$ чисел $$$a_i$$$ — количество нейтронов в ядре $$$i$$$ ($$$1 \le a_i \le 10^9$$$).

В третьей строке через пробел дано $$$n$$$ чисел $$$b_i$$$ — количество протонов в ядре $$$i$$$ ($$$1 \le b_i \le 10^9$$$).

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

Гарантируется, что граф взаимодействий связен и образует дерево.

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

Выведите одно число — максимальный заряд, который может получить атом в результате проведения эксперимента.

Примеры

Входные данные
5 1
4 2 1 1 1
5 2 1 5 4
1 2
1 3
3 4
3 5
Выходные данные
2
Входные данные
4 1
4 2 2 1
1 1 1 1
1 2
2 3
3 4
Выходные данные
1

Примечание

В первом примере из входных данных на ядро атома $$$1$$$ подается заряд $$$1$$$. Опишем, какие максимальные заряды можно получить на каждом из ядер:

Максимальное возможное значение заряда достигается у ядра 4 и это $$$2$$$.