광산

수직으로 뻗은 광산에 $N$개의 방이 있다. 각 방에는 지상에 더 가까운 다른 방에서 이어지는 수직 통로가 정확히 하나씩 있다. 1번 방은 바깥과 바로 연결된다. 광산은 1번 정점을 루트로 하는 트리이다.

각 통로에는 점수가 있다. 점수는 여러 요인에 따라 정해지지만, 이 문제에서는 점수가 직접 주어진다. 통로를 지나는 일은 위험할 수 있어서 점수가 음수일 수도 있다.

각 방에는 광부가 일정 수만큼 있다. 광부 중 일부(0명일 수도 있다)를 골라 각자에게 수직 경로를 하나씩 배정하는 채굴 배정을 만들려고 한다. 수직 경로는 깊은 방향으로만 진행한다. 즉 정점에서는 자식 정점으로만 이동할 수 있다. 경로의 점수는 지나간 통로 점수의 합이다. 배정의 점수는 배정된 경로 점수의 합이다. 어느 광부에게도 경로를 배정하지 않으면 점수는 0이다.

각 방에는 경로가 그 방에서 끝나는 광부 수의 상한도 있다. 경로를 배정받지 못한 광부는 광산을 떠나며, 이 상한 계산에는 포함되지 않는다.

트리, 각 방의 초기 광부 수, 각 방에서 끝날 수 있는 광부의 최대 수가 주어질 때 채굴 배정의 점수 최댓값을 구하라.

첫 줄에 방의 수 $N$이 주어진다. 둘째 줄에는 각 방의 초기 광부 수 $s_1, \cdots, s_N$이 주어진다. 셋째 줄에는 각 방에서 끝날 수 있는 광부의 최대 수 $e_1, \cdots, e_N$이 주어진다. 이어지는 $N-1$개의 줄에는 각각 $p_{i+1}$과 $w_{i+1}$이 주어지며, 이는 방 $p_{i+1}$에서 방 $i+1$로 점수가 $w_{i+1}$인 통로가 있다는 뜻이다.

채굴 배정의 점수 최댓값을 한 줄에 출력한다.

• $2 \le N \le 5 \times 10^5$
• 모든 $1 \le i \le N$에 대해 $0 \le s_i, e_i \le 2000$
• 모든 $2 \le i \le N$에 대해 $1 \le p_i < i$
• 모든 $2 \le i \le N$에 대해 $|w_i| \le 2000$

가능한 해 중 하나는 다음과 같다.

1. $1 \to 2 \to 4$, 점수 8
2. $1 \to 2 \to 4$, 점수 8
3. $1 \to 2$, 점수 6
4. $1 \to 2 \to 5$, 점수 5
5. $1 \to 2 \to 5$, 점수 5