12965번 - 빨간 선분 파란 선분

평면 위에 N개의 서로 다른 점이 있다. 점은 0번부터 N-1번까지 번호가 매겨져 있다.

오늘은 점과 점을 연결하는 선분을 긋는 게임을 하려고 한다. 게임은 총 두 단계로 이루어져 있다.

첫 번째 단계는 점을 먼저 빨간색이나 파란색으로 칠하는 것이고, 두 번째 단계는 선분을 0개 또는 그 이상 그리는 것이다.

모든 선분은 같은 색 점 두 개를 연결해서 만들 수 있으며, 점과 같은 색으로 그려야 한다.

같은 색을 갖는 선분은 접하거나 교차할 수 있지만, 다른 색을 갖는 선분은 접하거나 교차하면 안 된다. 즉, 빨간 선분은 파란 선분과 접하거나 교차하면 안 된다.

i번 점과 j번 점을 연결하는 빨간 선분의 점수는 red[i][j]점이고, 파란 선분의 점수는 blue[i][j]이다.

선분을 그려서 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 점의 개수 N (2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 점의 좌표 (x, y)가 주어진다. (-1000 ≤ x, y ≤ 1000) 같은 점이 여러 번 주어지는 경우는 없다.

다음 N개의 줄에는 빨간 선분의 점수를 나타내는 red[i][j]가 주어지고, 다음 N개의 줄에는 blue[i][j]가 주어진다. (0 ≤ red[i][j], blue[i][j] ≤ 100,000)

모든 0 ≤ i < N에 대해서, red[i][i] = 0, blue[i][i] = 0이고, 모든 0 ≤ i, j < N에 대해서, red[i][j] = red[j][i], blue[i][j] = blue[j][i]를 만족한다.

첫째 줄에 선분을 그어서 얻을 수 있는 최대 점수를 출력한다.

예제 1의 경우에 모든 점을 파란색으로 칠하고, 모든 파란 선분을 그어버리면 2+3+7+4+6+5 = 27점을 얻게 된다.