불안정성

강 건너편 소나무 숲은 한 시간 전만 해도 5월 햇살에 환했지만, 이제는 흐려지고 번져서 사라졌다. 남은 것은 정점이 $N$개인 거대한 나무 한 그루뿐이다. 이 나무는 1번 정점에 단단히 뿌리를 내리고 있다.

119호 방에 있던 이반은 이 나무를 바라보고 있었다. 자세히 보니 각 정점 $i$에 수 $a_i$가 적혀 있었다. 그때 $k$-좋은 부분트리라는 정의가 떠올랐다. 부분트리가 $k$-좋다는 것은, 부모 $u$와 자식 $v$를 잇는 모든 간선 $(u, v)$에 대해 $a_v = (a_u + 1) \bmod k$가 성립하고, 부분트리의 모든 정점 $v$에 대해 $a_v < k$도 성립한다는 뜻이다. 각 자연수 $k$에 대해 $k$-좋은 나무의 불안정성 $f(k)$가 주어진다.

다시 나무를 보니, 마법의 톱을 오른손에 든 이반이 나무 앞에 떠 있었다. 이반은 몇 개의 가지를 자르기로 했다. 잘라낸 간선을 제거하면 나무가 여러 부분트리로 나뉜다. 이반은 이 부분트리마다 수 $k_i$를 하나씩 골라, 그 부분트리가 $k_i$-좋도록 했다. 잘라낼 간선의 집합과 각 부분트리의 $k_i$를 함께 정한 것을 절단이라고 부른다. 절단의 불안정성은 얻어진 모든 부분트리에 대한 $f(k_i)$의 합이다. 이반이 절단의 최소 불안정성을 구하도록 도와 달라.

첫 줄에 자연수 $N$이 주어진다. 나무의 정점 개수이다. 둘째 줄에는 $N$개의 정수가 주어지며, $i$번째 수는 $a_i$이다 ($0 \le a_i \le N-1$). 셋째 줄에는 $N$개의 정수가 주어지며, $k$번째 수는 $f(k)$이다 ($1 \le f(k) \le 10^9$). 다음 $N-1$개의 줄에는 나무의 간선 정보가 주어진다. $i$번째 줄에는 간선 $(u_i, v_i)$를 나타내는 두 정수 $u_i$, $v_i$가 주어진다 ($1 \le u_i, v_i \le N$, $u_i \ne v_i$).

절단의 최소 불안정성을 한 줄에 출력한다.