정원

Sashka는 도시 정원의 꽃을 관리한다. 정원에는 1부터 $N$까지 번호가 붙은 $N$개의 꽃밭이 있으며, 일부 꽃밭은 배관으로 연결되어 있다. 꽃밭은 정점, 배관은 간선이 되어 연결되고 사이클이 없는 무방향 그래프를 이룬다. 각 꽃밭에는 지하수를 퍼 올리는 펌프가 하나씩 설치되어 있다. 꽃밭 $x$의 펌프는 펌프 번호 $x$이다. 펌프 $x$가 $p$분 동안 작동하면, 그래프에서 $x$로부터 간선 $p-1$개 이내의 거리에 있는 모든 꽃밭에 물이 닿는다.

펌프는 차례로 하나씩 작동한다. 두 펌프가 동시에 작동하는 일은 없으며, 각 펌프는 한 번만 작동할 수 있다. 꽃밭은 어느 펌프에서든 물이 닿으면 물을 공급받은 것으로 본다. 펌프 $m$이 작동할 때는 최대 $t_m$분까지만 작동해야 하며, 그렇지 않으면 고장 날 수 있다. 작동 시간은 정수 분 단위여야 한다. 펌프는 모두 같은 종류이며, 1분 동안 작동하면 $c_1$유로, 2분 동안 작동하면 $c_2$유로가 드는 식으로 전기 요금이 든다. 작동하지 않는 펌프는 전기를 소비하지 않는다. Sashka는 모든 꽃밭에 물을 줄 수 있는 펌프 작동 조합 중 전기 요금이 가장 적은 경우를 찾아야 한다.

첫 줄에는 꽃밭 수이자 펌프 수인 정수 $N$이 주어진다. 둘째 줄에는 공백으로 구분된 $N$개의 음이 아닌 정수 $c_1, c_2, \dots, c_N$이 주어지며, $c_k$는 펌프가 $k$분 동안 작동할 때의 전기 요금이다. 셋째 줄에는 공백으로 구분된 $N$개의 음이 아닌 정수 $t_1, t_2, \dots, t_N$이 주어지며, $t_m$은 펌프 $m$의 최대 작동 시간이다. 값이 0이면 그 펌프는 사용할 수 없다. 이어지는 $N-1$개의 줄에는 꽃밭 $u$와 $v$를 잇는 배관을 나타내는 양의 정수 두 개가 주어진다. 꽃밭과 배관은 연결되어 있고 사이클이 없는 그래프를 이룬다고 보장된다.

모든 꽃밭에 물을 줄 수 있는 경우의 전기 요금 최솟값을 표준 출력 한 줄에 출력한다. 모든 꽃밭에 물을 줄 수 없으면 $-1$을 출력한다.

$1 \le N \le 2000$

$0 \le c_i \le 10^6$

$0 \le t_i \le N$

그래프가 사슬이려면 그리고 그럴 때만, 모든 정점의 이웃이 최대 2개이고 이웃이 1개인 정점이 정확히 2개여야 한다.