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

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

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

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

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

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

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

입력 형식

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

둘째 줄부터 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

4
0 1
1 0
0 -1
-1 0
0 1 2 3
1 0 6 4
2 6 0 5
3 4 5 0
0 2 3 7
2 0 4 6
3 4 0 5
7 6 5 0

예제 출력 1

27

예제 입력 2

2
0 1
1 0
0 101
101 0
0 100
100 0

예제 출력 2

101

예제 입력 3

6
-3 0
-1 -2
-1 2
1 -2
1 2
3 0
0 2 1 2 1 2
2 0 2 1 2 1
1 2 0 2 1 2
2 1 2 0 2 1
1 2 1 2 0 2
2 1 2 1 2 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 21 0 0
0 0 21 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

예제 출력 3

25

예제 입력 4

6
-100 0
100 0
0 100
-10 10
10 10
0 1
0 96 96 25 25 25
96 0 96 25 25 25
96 96 0 25 25 25
25 25 25 0 10 10
25 25 25 10 0 10
25 25 25 10 10 0
0 30 30 20 20 20
30 0 30 20 20 20
30 30 0 20 20 20
20 20 20 0 86 86
20 20 20 86 0 86
20 20 20 86 86 0

예제 출력 4

546

힌트

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