시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB43816713136.490%

문제

온조는 N명의 참가자가 참가하는 프로그래밍 대결 대회를 열 것이다. 이 대회는 두 참가자가 일대일로 붙는 N-1개의 대결로 이루어진다. i번째 참가자는 실력 Ai를 가지고 있어 두 참가자가 대결을 할 때 더 높은 실력을 가진 참가자가 이기게 되고, 진 참가자는 탈락하여 더 이상 대결을 할 수 없게 된다. 단, 같은 실력을 가진 사람은 없다. 대결을 한 번 할 때마다 탈락하는 사람이 한 명씩 생기고, 이런 대결이 N-1개이기 때문에 끝까지 남는 사람은 한 명이고, 그 사람이 우승자가 된다.

이때, 실력 x를 가진 사람과 실력 y를 가진 사람이 대결할 때 대결의 흥미로움은 x ^ y로 정의된다. (^는 Bitwise XOR을 의미한다.) 또한 i번째 사람은 대결을 한 번 할 때마다 피로도가 Hi만큼 쌓이게 된다. 즉, i번째 사람이 대결을 총 k번 했다면 i번째 사람의 총 피로도는 Hi * k가 된다. 또한 i번째 사람은 최대 Li번의 경기를 할 수 있다. 단, 모든 i에 대해 Li ≥ 2이다.

온조는 대회를 최대한 재밌게 운영하려고 한다. 이때 (대회의 재미) = (모든 대결의 흥미로움의 합) - (모든 참가자들의 피로도의 합)으로 정의된다. (대회의 재미가 음수가 될 수 있다는 사실에 유의하자.) 참가자들이 대결하는 순서와 방법에 따라 대회의 재미가 결정되기 때문에 온조는 어떻게 대회를 운영할지 고민에 빠졌다.

예를 들어 실력이 각각 1, 3, 5이고, H값이 각각 6, 2, 4이며, L값이 각각 2, 2, 2인 3명의 참가자가 프로그래밍 대결 대회에 참가했다고 하자. 먼저 1번 참가자와 2번 참가자가 대결하면 실력이 더 높은 2번 참가자가 이기고, 1번 참가자는 탈락한다. 이때 (대결의 흥미로움) = A1 ^ A2 = 1 ^ 3 = 2가 된다. 그 다음 2번 참가자와 3번 참가자가 대결하면 실력이 더 높은 3번 참가자가 이기고, 2번 참가자가 탈락한다. 이때 (대결의 흥미로움) = A2 ^ A3 = 3 ^ 5 = 6이다. (모든 대결의 흥미로움의 합) = 2 + 6 = 8이 되고, 각 참가자들은 경기를 1번, 2번, 1번씩 했으므로 (모든 참가자들의 피로도의 합) = 6×1 + 2×2 + 4×1 = 14이다. 그래서 (대회의 재미) = 8 - 14 = -6이 된다. 또한 모든 참가자들은 Li번 이하로 경기를 했기 때문에 모든 조건을 만족한다. 모든 조건을 만족하면서 이보다 대회의 재미를 크게 할 수 있는 방법은 없다.

온조를 도와 N, A1 ~ AN, H1 ~ HN, L1 ~ LN이 주어질 때, 모든 조건을 만족하도록 대회의 재미를 최대화하여라.

입력

첫째 줄에 N (2 ≤ N ≤ 300)이 주어진다. 둘째 줄에 N개의 수 A1 ~ AN이 주어진다. (1 ≤ Ai ≤ 106) 셋째 줄에 N개의 수 H1 ~ HN이 주어진다. (1 ≤ Hi ≤ 106) 마지막 줄에 N개의 수 L1 ~ LN이 주어진다. (2 ≤ Li ≤ N-1)

출력

첫째 줄에 모든 조건을 만족시키면서 만들 수 있는 대회의 재미의 최댓값을 출력하여라.

예제 입력 1

3
1 3 5
6 2 4
2 2 2

예제 출력 1

-6

출처

Contest > BOJ User Contest > 소프트콘 > 제1회 소프트콘 D번