물류회사

문제

물류 회사 ana에는 $1$번부터 $N$번까지 번호가 붙은 지점 $N$개가 있다. 각 지점에는 본사로 보내야 할 운송물이 쌓여 있다.

$1$번을 제외한 각 지점에는 본사 방향의 다른 지점으로 향하는 일방통행 도로가 하나씩 안내되어 있다. 회사의 트럭은 이 도로만 이용한다. $1$번 지점 옆에는 본사가 있어, 트럭은 $1$번 지점까지의 수거를 마치면 본사에 도착하여 운행을 종료한다.

전체 도로망은 아래의 그림과 같이 $1$번 지점을 루트로 하는 트리를 이룬다. 따라서 어느 지점에서 출발하더라도 안내된 도로를 따라가면 본사에 도착한다.

처음에 $i$번 지점에는 운송물 $x_i$개가 있다. 트럭이 실어 간 운송물은 해당 지점에서 사라지며 다시 공급되지 않는다.

$Q$대의 트럭이 입력으로 주어진 순서대로 한 대씩 운행한다. $j$번째 트럭은 $v_j$번 지점에서 빈 상태로 출발하며, 운송물을 최대 $t_j$개까지 실을 수 있다. 트럭은 출발 지점부터 부모 지점을 차례로 거쳐 $1$번 지점까지 이동하며 다음 규칙으로 운송물을 싣는다.

1. 방문한 지점에 운송물이 있고 적재 공간이 남아 있다면, 남은 적재 공간만큼 최대한 싣는다.
2. 운송물이 없는 지점은 건너뛰고 다음 지점으로 이동한다. 적재 공간이 가득 차면 더 이상 싣지 않고 본사까지 이동한다.

각 트럭이 본사에 도착했을 때 실은 운송물의 수와 모든 트럭이 옮긴 운송물의 총합을 구해 보자.

입력

첫째 줄에 지점의 수 $N$과 트럭의 수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 100,000; 1 \le Q \le 200,000)$

둘째 줄에 $N-1$개의 정수 $p_2, p_3, \ldots, p_N$이 공백으로 구분되어 주어진다. $N=1$이면 둘째 줄은 빈 줄이다. $p_i$는 $i$번 지점에서 본사 방향으로 한 번 이동했을 때 도착하는 부모 지점의 번호다. $(1 \le p_i \le N)$ 주어진 지점과 길은 $1$번 지점을 루트로 하는 트리를 이룬다.

셋째 줄에 $N$개의 정수 $x_1, x_2, \ldots, x_N$이 공백으로 구분되어 주어진다. $x_i$는 처음에 $i$번 지점에 놓인 운송물의 수다. $(2 \le x_i \le 10^9)$

다음 $Q$개의 줄 중 $j$번째 줄에는 두 정수 $v_j$와 $t_j$가 공백으로 구분되어 주어진다. 이는 $j$번째 트럭이 $v_j$번 지점에서 출발하며, 최대 $t_j$개의 운송물을 실을 수 있음을 뜻한다. $(1 \le v_j \le N; 2 \le t_j \le 10^9)$

출력

첫째 줄부터 $Q$개의 줄에 걸쳐, $j$번째 줄에 $j$번째 트럭이 실은 운송물의 수를 출력한다.

마지막 줄에 모든 트럭이 실은 운송물의 총합을 출력한다.

예제 1

6 5
1 1 2 2 3
4 2 6 2 4 2
4 6
5 8
6 4
6 10
4 2

출력 1

6
6
4
4
0
20