방문

Byteasar는 대단한 사람이다. 지난 21년 동안 그는 우체부, 은행원, 아이스 스케이터, 심지어 왕이기도 했다! 그가 친구가 많은 것도 당연하다. 아니, 많았다. 직업과 직장이 계속 바뀌는 바람에 그는 많은 옛 친구들과 연락이 끊겼다. . . 이제 그것을 바꿀 때가 되었다! Bytasar는 옛 우정을 되살리기 위해 Byteotia 전역을 도는 대장정을 시작하려 한다.

Byteotia에는 n개의 도시가 있고, n−1개의 양방향 도로로 연결되어 있다. 우리의 주인공은 모든 도시를 방문하려 하며, 방문 순서는 이미 정해 두었다. 일정상 한 도시에서 다음 도시로 갈 때 그는 BMW(Byteotian Motor Wagons)에서 빌린 차를 운전한다. 대여는 전부 무료지만, 차에 연료를 넣어야 한다. 용량 k인 연료 탱크를 가진 차는 맨 처음에 연료를 채운 뒤, 도로를 k번 지날 때마다 다시 연료를 넣어야 한다. BMW는 Byteasar의 계획과 그가 가능한 한 빨리 여행을 끝내려 한다는 사실을 잘 알고 있다. 그래서 그들은 대여 차량의 탱크 용량을 교묘하게 정해서, Byteasar가 모든 도시에서 두 대의 차에 연료를 넣어야 하도록 만들었다. 그가 타고 도착한 차와 그가 타고 떠나는 차다. 처음 도시와 마지막 도시에서는 차 한 대에만 연료를 넣으면 된다.

Byteasar의 일정, 연료 가격, 탱크 용량을 알 때, 경로의 각 구간에 드는 비용을 구하라.

표준 입력의 첫 줄에는 Byteotia의 도시 수를 나타내는 정수 n (2 ≤ n ≤ 50 000) 하나가 주어진다. 도시는 1부터 n까지 번호가 붙어 있다. 다음 줄에는 n개의 정수 c1, . . . , cn (1 ≤ ci ≤ 10 000)이 단일 공백으로 구분되어 주어지며, Byteotia 모든 도시의 연료 가격을 나타낸다. 수 ci는 도시 i에서 어떤 차든 탱크를 채우는 비용이다. 이는 "뷔페식 주유", 즉 "ci만 내면 원하는 만큼 채울 수 있다"이다.

그 다음 n − 1개의 줄은 Byteotia의 도로망을 나타낸다. 각 줄에는 단일 공백으로 구분된 두 정수 a와 b (1 ≤ a, b ≤ n)가 주어지며, 도시 a와 b를 잇는 양방향 도로가 있다는 뜻이다.

그 다음 줄에는 n개의 정수 t1, . . . , tn이 단일 공백으로 구분되어 주어지며, Byteasar가 도시를 방문할 순서를 나타낸다. 1부터 n까지의 각 수가 이 순서에 정확히 한 번씩 나타난다. 마지막 줄에는 n − 1개의 정수 k1, . . . , kn−1이 단일 공백으로 구분되어 주어지며, 대여 차량의 탱크 용량을 나타낸다. 수 ki는 도시 ti에서 도시 ti+1로 갈 때, 도로를 ki번 지날 때마다 차에 연료를 넣어야 한다는 뜻이다. ki는 항상 그 두 도시 사이의 거리를 나누어떨어진다고 가정해도 좋다.

총점의 36%에 해당하는 테스트에서는 n ≤ 10 000이다. 그중 총점의 28%에 해당하는 일부 테스트에서는 더 강한 조건 n ≤ 1000이 성립한다.

프로그램은 표준 출력에 n − 1개의 줄을 출력하며, 각 줄에는 정수 하나가 들어가야 한다. i번째 줄의 수는 도시 ti에서 도시 ti+1로 가는 동안 연료를 넣는 데 드는 총비용이어야 한다.