육각형 콜로니

우주선 노스트로모의 임무 중 하나는 켄타우루스자리의 행성 MX8-26B 궤도에 영구 기지를 세우는 것이다. 기지는 단지를 이어서 만들고, 단지 하나는 똑같은 모양의 육각형 방을 변끼리 붙여 놓은 덩어리다. 방의 여섯 변에는 각각 구멍이 하나 있다. 완성된 기지에서 그 변에 다른 방이 붙어 있으면 구멍은 통로가 되고, 아무것도 붙어 있지 않으면 창문이 된다. 방을 붙이는 방법이 여러 가지이므로 단지 모양도 여러 가지다.

여행자들은 모양마다 정해진 개수의 단지를 가지고 있다. 완성된 기지에서 방 하나는 그 방의 창문 수와 같은 인원을 수용한다. 단지는 평면에서 마음대로 옮기고 돌려서 놓을 수 있지만 서로 다른 단지의 방이 겹쳐서는 안 되고, 완성된 기지는 하나로 이어져 있어야 한다. 서로 다른 단지가 맞대는 벽의 수는 연결에 필요한 최솟값까지 줄일 수 있다고 가정한다.

가지고 있는 단지의 목록이 주어질 때, $P$명 이상을 수용하는 기지를 세울 수 있는지 판정하는 프로그램을 작성하시오. 가지고 있는 단지를 모두 쓸 필요는 없다.

첫째 줄에 테스트 케이스의 수 $N$이 주어진다. 각 테스트 케이스의 첫째 줄에는 양의 정수 $P$와 $T$가 공백으로 구분되어 주어진다 ($P \le 1000000$, $T \le 1000$). $P$는 기지가 수용해야 하는 인원이고, $T$는 쓸 수 있는 단지 모양의 수다.

다음 $T$개의 줄에는 단지 모양 하나를 나타내는 정수가 공백으로 구분되어 주어진다. 각 줄의 처음 두 정수는 $C$와 $S$다 ($0 \le C \le 1000$, $1 \le S \le 1000$). $C$는 이 모양의 단지를 몇 개 가지고 있는지, $S$는 단지를 이루는 방의 수다. 모든 단지는 하나로 이어져 있고, 방의 육각형 바닥면은 모두 한 평면에 놓인다.

같은 줄의 나머지에는 $S$쌍의 정수가 온다. 각 쌍은 육각 좌표계에서 바닥면 중심의 $x$좌표와 $y$좌표다 ($-10000000 \le x, y \le 10000000$). 육각 좌표계의 $x$축은 직교 좌표계의 $x$축과 $-30^\circ$를 이루고, 육각 좌표계의 $y$축은 직교 좌표계의 $x$축과 $+30^\circ$를 이룬다. 따라서 좌표가 $(x, y)$인 방은 $(x+1, y)$, $(x-1, y)$, $(x, y+1)$, $(x, y-1)$, $(x+1, y-1)$, $(x-1, y+1)$에 있는 여섯 방과 벽을 맞댄다.

각 테스트 케이스마다 정확히 한 줄을 출력한다. $P$명 이상을 수용하는 기지를 세울 수 있으면 Je treba X celku.를 출력한다. 여기서 X는 모양과 연결 방식을 가장 좋게 골랐을 때 필요한 단지 수의 최솟값이다. 세울 수 없으면 Kapacita zakladny je pouze X lidi.를 출력한다. 여기서 X는 가지고 있는 단지를 모두 써서 가장 좋게 지은 기지가 수용하는 최대 인원이다.