Cupid's Perfect Match

At midnight on Valentine's Day, Cupid begins his work. He is given an equal number of men and women. Through a mystic sense he determines the fate value between each pair of a man and a woman, and he wants to shoot his special arrows so that every person is shot exactly once, and the sum of fate values over all pairs is maximized.

However, even with his magical modifications, Cupid's arrows have two limitations:

1. The range of the bow is limited — it cannot reach arbitrarily far.
2. The arrow travels in a straight line. This means that, for a candidate pair (a man and a woman), if there exists any other person lying strictly between them on the straight line joining them, then Cupid cannot pair them. In other words, if for points \((x_1,y_1)\) and \((x_2,y_2)\) the vector formed by any other point \((x,y)\) is collinear and lies strictly between the two endpoints (i.e. \(0 < (x-x_1, y-y_1)\cdot(x_2-x_1, y_2-y_1) < (x_2-x_1)^2+(y_2-y_1)^2\)), then that edge is blocked.

Your task is to help Cupid find the best way to shoot his arrows so that every person is paired, and the total fate value of the paired couples is maximized. If no perfect pairing exists obeying the above geometric constraint, output -1.

The fate values of a man and a woman pair are provided in a fate matrix.

Note: All formulas are given in LaTeX format. In particular, a point \((x,y)\) is said to lie strictly between \((x_1,y_1)\) and \((x_2,y_2)\) if

[ 0 < (x-x_1,\ y-y_1) \cdot (x_2-x_1,\ y_2-y_1) < (x_2-x_1)^2+(y_2-y_1)^2. ]

inputFormat

The input begins with an integer \(n\) representing the number of men (and the number of women). The next \(n\) lines each contain two integers representing the coordinates of each man. The following \(n\) lines each contain two integers representing the coordinates of each woman. Finally, there are \(n\) lines each containing \(n\) integers: the \(j\)th integer of the \(i\)th line is the fate value between the \(i\)th man and the \(j\)th woman.

Constraints: \(1 \leq n \leq 10\) (to allow exponential solutions), and all coordinates and fate values are integers.

outputFormat

If a perfect matching that obeys the geometric constraint exists, output the maximum total fate value. Otherwise, output -1.

sample

1
0 0
1 1
5

5