16858번 - 고양이 소개팅 서브태스크

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

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

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

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

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

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

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

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

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

1 ≤ n ≤ 5000이다.

1 ≤ i ≤ n인 i에 대해 양의 정수인 v_i는 모두 동일하다.

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