소들의 아코디언과 밴조 오케스트라

$2N$마리($3 \le N \le 1000$)의 소가 모여 오케스트라를 이루었습니다. 아코디언 연주자 $N$명과 밴조 연주자 $N$명입니다. $i$번째 아코디언 연주자의 재능 수치는 $A_i$, $j$번째 밴조 연주자의 재능 수치는 $B_j$이며, $0 \le A_i \le 1000$, $0 \le B_j \le 1000$입니다.

농부는 아코디언 연주자와 밴조 연주자를 짝지어 공연을 엽니다. $i$번째 아코디언 연주자와 $j$번째 밴조 연주자를 짝지으면 기부금으로 정확히 $A_i \cdot B_j$ 달러를 얻습니다.

연주자들은 원래 자리 순서를 고집하므로, 짝은 순서를 지켜야 합니다. 즉 $i$번째 아코디언 연주자가 $j$번째 밴조 연주자와 짝지어지면, $i$보다 큰 번호의 아코디언 연주자는 $j$보다 작은 번호의 밴조 연주자와 짝지어질 수 없습니다. 다시 말해, 선택한 짝들을 아코디언 연주자 번호의 오름차순으로 나열하면 밴조 연주자 번호도 반드시 증가해야 합니다. 그 결과 일부 소는 짝을 이루지 못할 수 있습니다.

짝을 이루지 못한 소는 속상해합니다. 아코디언 연주자들만 따로 보고, 짝이 없는 연주자들을 연속한 번호로 이루어진 극대 그룹으로 나눕니다. 재능 수치의 합이 $S$인 그룹은 $S^2$ 달러를 소비합니다(오렌지 소다로 슬픔을 달래는 비용). 밴조 연주자들에게도 같은 규칙이 독립적으로 적용됩니다.

정확히 말하면, $x$번째부터 $y$번째까지의 아코디언 연주자가 모두 짝이 없고 하나의 극대 연속 그룹을 이루면 $(A_x + A_{x+1} + \cdots + A_y)^2$ 달러를 소비하며, 밴조 연주자에게도 동일한 관계가 성립합니다.

이 비용은 농부가 부담하므로, 짝을 정할 때 이를 함께 고려합니다. 농부가 얻을 수 있는 최대 순이익(총 기부금에서 총 소다 비용을 뺀 값)을 구하세요.

• 첫째 줄에 정수 $N$이 주어집니다.
• 다음 $N$개의 줄에 $A_1, A_2, \ldots, A_N$이 한 줄에 하나씩 주어집니다.
• 그다음 $N$개의 줄에 $B_1, B_2, \ldots, B_N$이 한 줄에 하나씩 주어집니다.

농부가 얻을 수 있는 최대 순이익을 정수 하나로 출력합니다.

예시 풀이: 재능 수치가 각각 $1, 1, 5$인 아코디언 연주자 세 명과 $5, 1, 1$인 밴조 연주자 세 명이 있다고 합시다. 최선의 방법은 3번 아코디언 연주자(재능 $5$)와 1번 밴조 연주자(재능 $5$)를 짝지어 $5 \times 5 = 25$ 달러를 얻는 것입니다. 짝이 없는 두 아코디언 연주자(재능 $1$, $1$)는 하나의 그룹을 이루어 $(1 + 1)^2 = 4$ 달러를, 짝이 없는 두 밴조 연주자(재능 $1$, $1$)도 또 하나의 그룹을 이루어 $(1 + 1)^2 = 4$ 달러를 소비합니다. 따라서 순이익은 $25 - 4 - 4 = 17$입니다.

모든 $i$에 대해 $i$번째 아코디언 연주자와 $i$번째 밴조 연주자를 짝짓는 것은 항상 유효한 선택이므로, 정답은 절대 음수가 되지 않습니다. 기부금과 비용이 커질 수 있으므로 64비트 정수가 필요합니다.