시계 장치

셀레스트 산에는 $1$번부터 $N$번까지 번호가 붙은 $N$개의 시계 장치가 있다. 이 시계 장치들은 $N-1$개의 전선을 통해 모두 서로 연결되어 있다. 각 시계 장치는 $1$시부터 $12$시까지 총 $12$가지 중 하나의 시각을 가리킬 수 있다.

시계 장치에는 태엽이 있어, 전선을 통해 연결된 모든 시계 장치의 시간을 한 시간 단위로 돌릴 수 있다. 이때 $12$시에서 $1$시간이 지나면 $1$시가 된다. 두 시계가 전선을 통해 연결되어 있다는 것은 하나 이상의 전선을 거쳐 한 시계에서 다른 시계까지의 경로가 존재한다는 뜻이다.

현재 시각은 $12$시이다. 하지만 현재 $i$번째 시계 장치는 $D_i$시를 가리키고 있다. 만약 $i$번째 시계 장치가 $12$시를 가리키게 맞출 수 있다면, 당신은 그 시계 장치를 올바르게 맞춘 보수로 금화 $W_i$개를 받는다.

처음에 시계 장치들은 모두 연결되어 있으므로, 모든 시계 장치들은 똑같이 돌아간다. 당신은 더 많은 시계를 올바르게 맞추기 위해 전선을 원하는 만큼 끊을 수 있다. 그러나, 하나의 전선을 끊을 때마다 받는 보수는 금화 $C$개만큼 줄어든다.

당신이 보수로 받을 수 있는 금화의 최대 개수는 몇 개일까?

첫 번째 줄에 시계 장치의 수 $N$과 전선을 끊는 데 드는 비용 $C$가 주어진다.

두 번째 줄에 현재 시계 장치가 가리키고 있는 시각 $D_i$가 차례대로 주어진다. ($1 \le i \le N$)

세 번째 줄에 시계 장치를 올바르게 맞추었을 때의 보수 $W_i$가 차례대로 주어진다. ($1 \le i \le N$)

그 다음 $N-1$개의 줄에 시계 장치를 잇는 전선의 번호 $U_i$와 $V_i$가 차례로 주어진다. ($1 \le i \le N - 1$)

이는 $U_i$번 시계 장치와 $V_i$번 시계 장치가 전선으로 이어져 있다는 뜻이다.

첫 번째 줄에 당신이 벌어들일 수 있는 금화의 최대 개수를 출력한다.

• $1 \le N \le 100\,000$
• $1 \le C \le 10^9$
• $1 \le D_i \le 12$ ($1 \le i \le N$)
• $1 \le W_i \le 10^9$ ($1 \le i \le N$)
• $1 \le U_i, V_i \le N$ ($1 \le i \le N - 1$)