내가 그린 라이언 그림

나는 라이언 그림들을 그려, 트리 형태의 구조를 띄고 있는 미술관에 전시해 두었다. 미술관은 여러 방으로 이어져 있으며 각 방에 하나의 그림이 있다. 그 방을 오갈 수 있는 여러 길이의 통로들이 있는데, 방을 정점으로, 통로를 간선으로 한다면 그 그래프가 트리라는 것이다. 트리에서의 루트는 입장 및 퇴장을 할 수 있는 문이 있는 1번 방이다. 

그런데 슬프게도 누군가가 침입해 모든 라이언 그림이 곰처럼 보이게 해버렸다. 나는 정확히 N개의 라이언 그림을 그렸는데, 그 종류는 총 K개가 있다. i번째 종류의 그림을 수정할 때 Ci만큼의 시간이 소모된다. 그리고 물감의 양은 한정되어 있기에 i번째 종류의 그림은 Pi개만 수정할 수 있다. 

또한, 1번 방을 루트로 하였을 때 한 방을 “작업 방”으로 정한다. 나는 작업 방을 루트로 하는 서브트리 내의 그림들만을 수정할 수 있다. 그리고 작업을 끝낼 때마다 작업 방으로 되돌아가야 하므로, 작업 방에서 그림이 원래 있던 곳까지의 거리가 d라고 할 때, d만큼의 시간이 추가로 필요하다. 나는 M시간 동안 작업을 할 수 있다. 각각의 방을 작업 방으로 삼을 때, 작업 시간의 합이 M을 초과하지 않게 수정할 수 있는 그림의 최대 개수는 무엇인지 알려주길 바란다.

첫째 줄에는 N, K, M이 주어진다. (1 ≤ K ≤ N ≤ 2 × 105, 1 ≤ M ≤ 1015)

N-1개의 줄에 걸쳐, i번째 정보로 i+1번 방의 부모 방의 번호와 부모 방까지의 거리가 공백으로 구분되어 주어진다. (1 ≤ 통로의 길이 ≤ 105)

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

다음 줄에 K개의 수가 주어지며, i번째 수는 Ci를 의미한다. (1 ≤ Ci ≤ M)

다음 줄에 K개의 수가 주어지며, i번째 수는 Pi를 의미한다. (1 ≤ Pi ≤ N)

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