시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 1024 MB 56 14 10 47.619%

문제

류트나라에는 거대한 캣타워가 있다. 캣타워는 루트 있는 트리 구조를 이루고 있다. 따라서 캣타워에는 1번부터 n번까지 번호가 붙여진 총 n개의 보금자리가 있고, 보금자리에 연결된 n-1개의 통로가 있다. 캣타워의 맨 위에는 항상 1번 보금자리가 있다. 캣타워에 사는 고양이들은 아래쪽 통로를 통해서 살던 보금자리에서 다른 보금자리로 떨어질 수 있다. 단, 고양이들이 통로를 타고 올라갈 수는 없다. 캣타워가 루트 있는 트리 구조이기 때문에, 맨 위 보금자리를 제외하면 임의의 보금자리로 곧바로 떨어질 수 있는 통로는 단 하나 존재한다. 또한 어떤 보금자리에서 다른 보금자리로 떨어질 수 있다면 그 경로는 유일하며, 모든 보금자리는 통로로 이어져 있다.  i번 보금자리에는 암컷 또는 수컷 고양이가 ci마리 살고 있다. i번 보금자리로 곧바로 떨어질 수 있는 통로는 길이가 di이다. 한 보금자리에서 다른 보금자리로 이동하는 경로의 길이는 한 통로를 두 번 이상 지나지 않으면서 이동할 때 지나게 되는 모든 통로의 길이의 합이 된다.

고양이들은 오늘 단체로 소개팅을 하려고 한다. 고양이들의 소개팅 한 쌍은 암컷 고양이 한 마리와 수컷 고양이 한 마리가 만나서 이뤄진다. 소개팅에 가기 위해서 수컷 고양이는 아래쪽 통로를 통해 이동할 수 있는 보금자리로 뛰어내릴 수 있다. 하지만 공중 곡예비행의 대가라고 불리는 고양이들도 너무 많이 떨어지면 다치기 때문에, i번 보금자리에 사는 고양이들은 원래 살던 보금자리로부터 경로의 길이가 vi를 초과하는 정점으로는 뛰어내리지 않기로 했다. 시장 leejseo는 가능한 많은 쌍의 소개팅이 이뤄지길 원한다. leejseo는 어떻게 하면 소개팅 횟수를 최대화 할 수 있을까 고민하다, 당신에게 그 작업을 맡기기로 했다. 캣타워의 구조와 고양이들의 정보가 주어질 때, 성사될 수 있는 소개팅 횟수의 최댓값을 구하시오.

입력

첫 번째 줄에 캣타워 내 보금자리의 개수 n (1 ≤ n ≤ 200,000)이 주어진다. 

두 번째 줄에 1번 보금자리부터 n번 보금자리에 사는 고양이의 수 ci (1 ≤ ci ≤ 108)가 차례대로 주어진다.

세 번째 줄에, 1번 보금자리부터 n번 보금자리에 사는 고양이가 떨어질 수 있는 최대 높이 vi (vi는 -1이거나 1 ≤ vi ≤ 108)가 차례대로 주어진다. 만약 vi가 1 이상의 정수라면, i번 보금자리에는 ci마리의 수컷 고양이가 살고 있다. vi가 -1이라면, 그 보금자리에는 ci마리의 암컷 고양이가 살고 있다.

네 번째 줄에 2번 보금자리부터 n번 보금자리까지 그 보금자리로 곧바로 떨어질 수 있는 보금자리 ai (1 ≤ ai ≤ n)가 차례대로 주어진다.

다섯 번째 줄에 2번 보금자리부터 n번 보금자리까지 그 보금자리로 곧바로 떨어질 수 있는 통로의 길이 di (1 ≤ di ≤ 108)가 차례대로 주어진다.    

출력

첫 번째 줄에 성사될 수 있는 소개팅 횟수의 최댓값을 출력하여라.

서브태스크 1 (18점)

2 ≤ i ≤ n인 i에 대해 ai=i-1이다.

서브태스크 2 (30점)

1 ≤ n ≤ 5000이다.

서브태스크 3 (42점)

1 ≤ i ≤ n인 i에 대해 vi는 모두 동일하다.

서브태스크 4 (60점)

추가적인 제약 조건이 없다.

예제 입력 1

5
5 4 3 6 2
-1 3 5 -1 5
3 1 2 1
4 1 3 2

예제 출력 1

4

2번 보금자리에서 수컷 고양이 4마리가 4번 보금자리로 떨어질 수 있다. 이때 성사되는 최대 소개팅 수는 4이다. 3번 보금자리에서 고양이가 뛰어내릴 수 있는 최대 높이는 5이기 때문에, 4번 보금자리까지 뛰어내릴 수 없다.

채점

  • 예제는 채점하지 않는다.