SPOJ in Gyumri

   An important task of the hyper-cosmic spaceship Nostromo is to establish a permanent base on the orbit of the planet MX8-26B in the Centaurus constellation. The base is built from complexes composed of identical hexagonal cubicles. Each of the six sides of each cubicle contains a hole serving either as a passage to a neighboring cubicle or as a window in case when no cubicle of the finished base is neighboring at this side. The complexes can be composed of the cubicles in many different ways.

   The travelers have a given number of complexes of several shapes at their disposition. Every cubicle in the finished base accommodates as many people as the number of windows it has.

   Write a program to determine whether it is possible to build a base for the prescribed number of people given the descriptions of available complexes.

Input

   The first line of the input contains the number of test cases N . The first line of each test case contains two space-separated positive integers P ≤ 1 000 000 and T ≤ 1000, where P is the number of inhabitants for whom the base is to be built and T is the number of shapes of available complexes.

   Each of the following T lines contains integers separated by spaces describing one shape of a complex. The first two numbers  on each of these lines are integers C and S, where C (0 ≤ C ≤ 1000) is the number of available complexes of this shape and S (1 ≤ S ≤ 1000) is the number of cubicles that make up the complex. It is known that every complex is connected and the hexagonal bottom bases of its cubicles lie in one plane.

Output

   For each test case, print exactly one line. If it is possible to build the base, the line says “Je treba X celku.”, where X is the minimal possible number of complexes when the shapes and their connections are chosen optimally. Otherwise print “Kapacita zakladny je pouze X lidi.”, where X is the maximal number of people that can fit inside the optimal base built from all of the available complexes.

Examples