A software developing company has been assigned two programming projects. As both projects are within the same contract, both must be handed in at the same time. It does not help if one is finished earlier.

This company has n employees to do the jobs. To manage the two projects more easily, each is divided into m independent subprojects. Only one employee can work on a single subproject at one time, but it is possible for two employees to work on different subprojects of the same project simultaneously. Our goal is to finish the projects as soon as possible.

Input starts with an integer T (≤ 12), denoting the number of test cases.

Each case starts with two integers n (1 ≤ n ≤ 100), and m (1 ≤ m ≤ 100). Each of the next n lines contains two integers which specify how much time in seconds it will take for the specified employee to complete one subproject of each project. So if the line contains x and y, it means that it takes the employee x seconds to complete a subproject from the first project, and y seconds to complete a subproject from the second project.

For each case, print the case number and the minimum amount of time in seconds after which both projects can be completed. The input will be such that answer will be within 50000.