The DOJ laboratory maintains types of microorganisms, numbered from to .
The population of type on day is , and it increases by each day. The value is called its growth coefficient. For example, if the initial population is and the growth coefficient is , the populations on days , , and are , , and , respectively.
Dadas, the director of the laboratory, wants to select some types of microorganisms as research samples on a certain day. The selected type numbers must appear in the same order under both of the following sorting methods.
Both methods break ties by placing the smaller type number first. Each ordering contains only the selected types.
Dadas wants to begin research on a day when at least types satisfying this condition can be selected.
Find the earliest day on which research can begin. The day must be a nonnegative integer. If it is impossible to select at least types on any day, output -1.
The input is given in the following format.
For each test case, output the earliest day on which at least types satisfying the condition can be selected, on a separate line. If there is no such day, output -1.
It can be proved that any answer other than -1 is between and , inclusive.
In the first test case, the populations on day are . For any two types, the one with the smaller growth coefficient has the larger population, so the two orders differ. On day , the populations are . If types and are selected, their growth-coefficient order is . Their populations are equal, so the smaller type number comes first and their population order is also . The answer is therefore .
is the number of test cases. Each test case is given in the following format.
The first line contains the number of types and the minimum number of types required for research .
The -th of the following lines contains the population of type on day and its growth coefficient .
| 2 | 21 | . |
| 3 | 29 | . |
| 4 | 37 | No additional constraints. |
In the second test case, at most one type can be selected on day . On day , all populations are , so all three types can be selected: both orders are . Selecting more than the required types is allowed, so the answer is .
In the third test case, selecting types and on day gives the order under both methods. The answer is therefore .
In the fourth test case, all growth coefficients are equal, so the populations always decrease as the type numbers increase. For any two types, the growth-coefficient order puts the smaller type number first, while the population order puts the larger type number first. Thus, two types can never be selected.
