|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||3||2||2||66.667%|
The octoplusplus is a very smart animal that can easily tell if it can escape from any given trap. Indeed, each octoplusplus has the knowledge of its own minimal section M: an octoplusplus can pass through any hole whose area is no less than M. (The octoplusplus is very flexible, so the shape of the hole does not matter: only the area does.) Hence, when trapped in a cage, the octoplusplus can escape if and only if one of the holes in the cage has area ≥ M.
Before his mission “Twenty Thousand Leagues Under the Sea”, professor Pierre Aronnax needs to capture such an animal. He has a set of N cubic cages. The walls of these cages are grids with rectangular holes. For each cage, Pierre knows the length and width of the biggest hole. Pierre also has special glasses that determine the minimal section of any octoplusplus that he sees.
Pierre has just seen a splendid octoplusplus and wants to trap it in the cage with the biggest hole (in terms of area) while ensuring that the octoplusplus cannot escape. Can you help him?
The input file consists of multiple test cases. The first line of the input file consists of a single integer indicating the number of test cases. Each test case follows. The first line of a test case consists of two integers M and N separated by a single space: 1 ≤ M ≤ 50 000 is the minimal section of the octoplusplus (in square millimeters), and 1 ≤ N ≤ 10 000 is the number of cages that Pierre owns. The rest of the test case consists of N lines. For 1 ≤ i ≤ N, the i-th line describes the i-th cage, and consists of two integers Li and Wi separated by a single space: 1 ≤ Li ≤ 1 000 is the length (in millimeters) of the biggest hole of the i-th cage, and 1 ≤ Wi ≤ 1 000 is the width (in millimeters) of that hole. It is never the case that the largest holes of two different cages have the same area.
For each test case in the input, your program should produce one line consisting of an integer 1 ≤ p ≤ N indicating the position (in the input) of the cage that satisfies Pierre’s wishes, i.e., has the biggest hole in terms of area, but ensures that the octoplusplus cannot escape. If the octoplusplus is too small and no cage is adequate, you should instead produce one line consisting of the string Too small (followed by a newline). There should be no blank lines in your output.
2 8 5 7 7 2 3 9 9 5 8 2 4 9 2 3 5 2 5
2 Too small