17831번 - 대기업 승범이네

문제

(주)승범이네는 사장 승범이를 포함한 N명의 직원이 모두 판매원인 다단계 회사이다. 사장 승범이를 제외한 모든 판매원에게는 사수가 한 명씩 배정된다. 만약 판매원 A가 B의 사수라면, B를 A의 부사수라고 부른다.

작년에 창설된 (주)승범이네는 큰 수익률을 기록하고 대기업으로 거듭났다. (주)승범이네의 더 큰 성장을 위해 멘토링 제도를 도입하려고 한다. 승범이는 사수와 부사수 관계에 있는 두 판매원을 각각 서로의 멘토와 멘티로 만들 수 있으며, 이 경우 두 판매원이 멘토링 관계에 있다고 한다. 한 판매원은 최대 1개의 멘토링 관계에만 속할 수 있다. 즉, 한 판매원이 여러 명의 멘토가 되거나, 여러 명의 멘티가 되거나, 멘토인 동시에 멘티가 될 수는 없다. 물론 멘토링 관계에 속하지 않는 직원이 있을 수도 있다.

이렇게 만들어진 멘토링 관계에서는 시너지 효과가 발생한다. 승범이는 모든 판매원의 실력을 수치화시켰으며, 한 멘토링 관계에서 발생하는 시너지는 멘토와 멘티의 실력의 곱과 같다는 것을 발견했다. 승범이는 적절하게 멘토링 관계를 만들어, 모든 멘토링 관계에서 발생하는 시너지의 합을 최대로 만들려고 한다.

위 그림은 (주)승범이네의 회사 구조와 멘토링 관계를 나타낸 예시이다. 각 원은 한 명의 판매원을 의미하며, 원 안에 쓰인 숫자는 그 판매원의 실력이다. 화살표는 사수-부사수 관계를 나타낸다. 이 경우 가능한 시너지의 최대 합은 5×7 + 4×3 + 3×3 + 4×5 + 3×1 = 79이다.

입력

첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다.

두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대로 공백으로 구분되어 주어진다.

세 번째 줄에 i번 판매원의 실력을 나타내는 정수 A₁, A₂, …, A_N (0 ≤ A_i ≤ 100)이 순서대로 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 모든 멘토링 관계에서 발생하는 시너지의 합의 최댓값을 출력한다. 만약 멘토링 관계가 하나도 성립될 수 없을 경우, 0을 출력한다.

제한

힌트