네트워크 요금

네트워크는 현대 사회에서 필수적인 요소가 되었다. 매일 수억 명의 사용자가 교육, 연구, 오락 등을 위해 웹을 이용한다. 네트워크 운영 비용이 막대하다는 점도 간과할 수 없다. 따라서 사용자에게 적절히 요금을 부과하는 것은 필요하고 합리적이다.

MY시 NS 고등학교에도 이런 교육 네트워크가 있다. 사용자는 $2N$명이며 $1, 2, 3, \ldots, 2N$번으로 번호가 매겨져 있다. 사용자 사이는 라우터와 케이블로 연결되어 있다. 사용자, 라우터, 케이블은 완전 이진 트리를 이룬다. 리프 노드는 사용자이고, 리프가 아닌 노드는 라우터이며, 간선은 네트워크 케이블이다.

이 회사는 pairwise charging이라는 방식으로 요금을 매긴다. 모든 사용자 쌍 $i$, $j$ ($1 \le i < j \le 2N$)에 대해 요금이 발생한다. 각 사용자는 요금제 A와 B 중 하나를 독립적으로 고르므로, 요금은 그 선택에 따라 달라진다. 총요금은 서로 다른 사용자 사이의 쌍별 요금을 모두 더한 값이다.

용어 정의는 다음과 같다.

• 조상: 루트 노드에는 조상이 없다. 루트가 아닌 노드의 조상은 부모 노드와 부모의 조상이다.
• 리프 포함: 리프 노드는 리프를 포함하지 않는다. 리프가 아닌 노드는 왼쪽 자식이 포함하는 리프 수와 오른쪽 자식이 포함하는 리프 수를 합한 만큼의 리프를 포함한다.
• 거리: 두 노드 사이의 거리는 두 노드를 잇는 가장 짧은 경로의 간선 수이다.

두 사용자 $i$, $j$ ($1 \le i < j \le 2N$)에 대해, 각 사용자와의 거리가 가장 짧은 공통 조상 라우터 $P$를 찾는다. 그다음 $P$가 포함하는 리프(사용자) 중 요금제 A를 고른 사람 수와 B를 고른 사람 수를 센다. 이를 각각 $n_A$, $n_B$라 한다. 요금은 아래 표에 따라 정해지며, $F_{i,j}$는 $i$와 $j$ 사이의 이미 알려진 데이터 흐름이다.

사용자들은 학교가 회사에 내는 총요금을 줄이려고 요금제를 바꾸고 싶어 한다. 회사는 등록 시점의 각 사용자 요금제를 기록해 두었다. 사용자 $i$가 요금제를 바꾸면(A에서 B로 또는 B에서 A로) 기록을 갱신하기 위해 $C_i$달러를 내야 한다.

처음 등록된 요금제와 비용 $C_i$가 주어질 때, 요금제 변경 비용과 쌍별 요금의 합이 가장 작아지도록 각 사용자의 요금제를 정하라.

첫째 줄에 양의 정수 $N$이 주어진다.

둘째 줄에는 사용자 $1, 2, \ldots, 2N$의 등록된 요금제가 $2N$개의 정수로 주어진다. 초기 요금제가 A이면 0, B이면 1이다.

셋째 줄에는 각 사용자가 요금제를 바꾸는 데 드는 비용(달러) $C_1, C_2, \ldots, C_{2N}$이 주어진다.

이후 $2N-1$개의 줄에 데이터 흐름표 $F$가 주어진다. $(i+3)$번째 줄의 $j$번째 정수가 $F_{i,j+i}$이다 ($1 \le i < 2N$, $1 \le j \le 2N-i$).

학교가 회사에 지불해야 하는 총액의 최솟값(달러)을 정수 하나로 출력한다.

$N \le 10$, $0 \le F_{i,j} \le 500$, $0 \le C_i \le 500\,000$.