Hexagonal colony

One task of the spaceship Nostromo is to set up a permanent base in the orbit of the planet MX8-26B in the Centaurus constellation. The base is built from complexes, and one complex is a block of identical hexagonal cubicles joined edge to edge. Each of the six sides of a cubicle has one hole in it. In the finished base the hole is a passage when another cubicle sits on that side, and a window when nothing sits there. Cubicles can be joined in many ways, so complexes come in many shapes.

The travelers carry a fixed number of complexes of each shape. In the finished base one cubicle takes as many people as it has windows. A complex can be moved and rotated freely in the plane, cubicles of different complexes must not overlap, and the finished base has to be connected in one piece. Assume the complexes can always be arranged so that the number of walls shared by different complexes is the smallest number connectivity allows.

Given the list of available complexes, decide whether a base that takes $P$ people or more can be built. The available complexes do not all have to be used.

The first line contains the number of test cases $N$. The first line of each test case contains two positive integers $P$ and $T$ separated by a space ($P \le 1000000$, $T \le 1000$). $P$ is the number of people the base has to take and $T$ is the number of shapes of available complexes.

Each of the next $T$ lines describes one shape with integers separated by spaces. The first two integers on the line are $C$ and $S$ ($0 \le C \le 1000$, $1 \le S \le 1000$), where $C$ is how many complexes of this shape are available and $S$ is the number of cubicles in the complex. Every complex is connected and the hexagonal bottom faces of its cubicles lie in one plane.

The rest of the line holds $S$ pairs of integers, the $x$ and $y$ coordinates of the centers of the hexagonal bottom faces in a hexagonal coordinate system ($-10000000 \le x, y \le 10000000$). The $x$-axis of the hexagonal coordinate system makes an angle of $-30^\circ$ with the $x$-axis of the Cartesian system, and the $y$-axis of the hexagonal coordinate system makes an angle of $+30^\circ$ with the $x$-axis of the Cartesian system. A cubicle at $(x, y)$ therefore shares a wall with the cubicles at $(x+1, y)$, $(x-1, y)$, $(x, y+1)$, $(x, y-1)$, $(x+1, y-1)$ and $(x-1, y+1)$.

Print exactly one line for each test case. If a base that takes $P$ people or more can be built, print Je treba X celku., where X is the smallest number of complexes needed when the shapes and their connections are chosen in the best way. Otherwise print Kapacita zakladny je pouze X lidi., where X is the largest number of people that fits in the best base built from all of the available complexes.