Gluing Gray Tiles

The game is played on an unbounded chessboard. There is a black obstacle at the center \( (0,0) \). Not far away, gray tiles are placed on N distinct cells, each having odd-valued coordinates. The goal of the game is to glue all the gray tiles together so that they form a given shape. The target shape is provided as a set of coordinates, and it can appear anywhere on the board (via translation only, no rotations or reflections are allowed). However, the final configuration must not cover the obstacle at \( (0,0) \) and the total number of moves performed (defined below) must not exceed 2000.

The move rules are as follows: In one move, you can choose one (or a connected group of) gray tile(s) and slide it one unit in one of the four cardinal directions (up, down, left, right). Tiles move along a Manhattan path and the cost (in moves) to slide a tile from point \( (x,y) \) to \( (x+\delta_x, y+\delta_y) \) is \( |\delta_x|+|\delta_y| \). Once two tiles become adjacent (share a side) they stick together and will move as a unit in subsequent moves. For this problem, we assume that the only allowed operation to achieve the target is to translate the given target shape to exactly match the positions of the gray tiles. In other words, there must exist an integer translation \( (t_x, t_y) \) such that when each coordinate \( (a,b) \) in the target shape is translated to \( (a+t_x, b+t_y) \) the resulting set is identical to the set of initial gray tile positions.

Moreover, if a tile moves from its target position by the translation \( (t_x,t_y) \), then its individual move cost is \( |t_x|+|t_y| \) and the total move cost for all gray tiles is \( N\times (|t_x|+|t_y|) \). You are to compute the total move cost if a valid translation exists and it does not exceed 2000; otherwise, output -1.

Note: The final positions must not include the obstacle at \( (0,0) \). You are guaranteed that all initial coordinates are odd numbers. The target shape can be anywhere on the board as long as it is translated without rotation or reflection.

inputFormat

The input consists of two parts:

1. The first part describes the initial positions of the gray tiles:
   • First line: an integer N (the number of gray tiles).
   • Next N lines: each contains two integers x and y indicating the position of a gray tile. All coordinates are odd and \( (0,0) \) is not among them.
2. The second part describes the target shape:
   • Next line: an integer N (the number of tiles in the target shape; will be equal to the number of gray tiles).
   • Next N lines: each contains two integers a and b representing the coordinates of a tile in the target shape (given relative to an arbitrary reference point).

outputFormat

Output a single integer: the total move cost, defined as \( N\times (|t_x|+|t_y|) \), if there exists an integer translation \( (t_x, t_y) \) such that the set \[ \{(a+t_x,\,b+t_y) : (a,b) \in \text{target shape}\} = \{(x,y) : (x,y) \text{ is an initial gray tile}\} \] and none of these positions is \( (0,0) \) (the obstacle position), and the total move cost does not exceed 2000. Otherwise, output -1.

sample

3
-1 -1
1 -1
1 1
3
-1 -1
1 -1
1 1

0