내가 그린 라이언 그림

나는 라이언 그림을 그려 트리 구조의 미술관에 전시해 두었다. 미술관은 여러 방이 통로로 이어져 있고, 각 방에는 그림이 한 점씩 있다. 방을 정점으로, 통로를 간선으로 놓으면 이 그래프는 트리다. 트리의 루트는 1번 방이며, 이 방에 입장과 퇴장이 가능한 문이 있다.

누군가 침입해 모든 라이언 그림을 곰처럼 보이게 만들었다. 나는 정확히 N개의 라이언 그림을 그렸고, 그림의 종류는 K가지다. i번째 종류의 그림 하나를 수정하는 데 $C_i$의 시간이 든다. 물감이 한정되어 있어서 i번째 종류의 그림은 $P_i$개까지만 수정할 수 있다.

1번 방을 루트로 할 때, 한 방을 작업 방으로 정한다. 작업 방을 루트로 하는 서브트리 안의 그림만 수정할 수 있다. 작업을 끝낼 때마다 작업 방으로 돌아가야 하므로, 작업 방에서 그림이 있던 곳까지의 거리가 d이면 d만큼의 시간이 추가로 든다. 작업할 수 있는 시간은 M이다. 각 방을 작업 방으로 정했을 때, 작업 시간의 합이 M을 넘지 않도록 수정할 수 있는 그림의 최대 개수를 구하라.

첫째 줄에 N, K, M이 주어진다. ($1 \le K \le N \le 2 \times 10^5$, $1 \le M \le 10^{15}$)

이어지는 N-1개의 줄에는 통로 정보가 주어진다. i번째 줄에는 i+1번 방의 부모 방 번호와 부모 방까지의 거리가 공백으로 구분되어 있다. ($1 \le$ 통로의 길이 $\le 10^5$)

다음 줄에는 N개의 수가 주어지며, i번째 수는 i번 방에 있는 그림의 종류다. ($1 \le$ 그림의 종류 $\le K$)

다음 줄에는 K개의 수가 주어지며, i번째 수는 $C_i$다. ($1 \le C_i \le M$)

다음 줄에는 K개의 수가 주어지며, i번째 수는 $P_i$다. ($1 \le P_i \le N$)

i번째 줄에 i번 방을 작업 방으로 했을 때 수정할 수 있는 그림의 최대 개수를 출력한다.