Three Objects Separation

For Bessie’s birthday, Farmer John presents her with a mechanical puzzle consisting of three objects. Each object is built from one or more 1×1 unit squares that are connected (that is, from any square you can reach any other square on the object by moving north, south, east, or west through adjacent squares). An object can be slid one unit at a time in any of the four cardinal directions. The goal of the puzzle is to make the objects "separated." Two objects are considered separated if the intersection of their bounding boxes has zero area. Here, each object’s bounding box is defined as the minimum axis‐aligned rectangle that covers all its unit squares; in particular, if an object covers squares with coordinates (x) and (y), its bounding box extends from (x_{min}) to (x_{max}+1) and from (y_{min}) to (y_{max}+1). Two bounding boxes do not have a positive overlap if either [ \text{box1}.right \le \text{box2}.left \quad\text{or}\quad \text{box2}.right \le \text{box1}.left \quad\text{or}\quad \text{box1}.top \le \text{box2}.bottom \quad\text{or}\quad \text{box2}.top \le \text{box1}.bottom ]

You are given the shapes and initial positions of the three objects. The shape of an object is given as a set of coordinates of its unit squares. The position is specified implicitly by the coordinates (i.e. the object in its initial state appears exactly at the given coordinates). Your task is to compute the minimum number of individual slides required to separate the three objects. A slide consists of moving one object by one unit in one of the four directions.

inputFormat

The first line contains three positive integers n₁ n₂ n₃, where n_i is the number of unit squares in object i (object 1, 2 and 3 respectively). Subsequently, there are n₁ lines each containing two integers giving the coordinates of the unit squares for object 1. This is followed by n₂ lines for object 2 and then n₃ lines for object 3. All coordinates are integers.

Note: The objects are given in their initial positions.

outputFormat

Output a single integer which is the minimum number of moves (slides) required to separate the objects so that no pair of objects have bounding boxes with positive overlap.

Note: Two bounding boxes are considered not overlapping if either they do not overlap horizontally or they do not overlap vertically. Each object’s bounding box is defined as [\(x_{min}, x_{max}+1\)] \(\times\) [\(y_{min}, y_{max}+1\)].

sample

1 1 1
0 0
2 0
0 2

0