Your exam is over and you are about to get your grade. You have got marks in n subjects and for each subject you are given two integers p_i and m_i, p_i is the mark you obtained and m_i is the total mark in i^th subject.

Now, your teacher is about to remove d of the subjects, and after that she will calculate your average grade by the following rule. She first adds the total marks m_i for the remaining subjects, let this summation be M. And then she adds the marks you obtained in those subjects, let this summation be P. So, your grade is (P/M) * 100.

Now, you requested your teacher to give you the permission to remove these d subjects by yourself and she agreed. So, given all the marks, your task is to remove exactly d subjects such that your average grade becomes as high as possible.

For example, there are three subjects and your marks are 5, 7 and 10 and the total marks in the subjects are 10, 20 and 15 respectively. And let d be 1. So, if you remove the second subject, your grade becomes 60% (15/25 * 100) which is the best you can do.

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

Each case starts with a blank line. Next line contains two integers n (2 ≤ n ≤ 20000) and d (1 ≤ d < n). Each of the next n lines contains two integers p_i and m_i (1 ≤ m_i ≤ 1000, 0 ≤ p_i ≤ m_i) where p_i is the mark you obtained and m_i is the total mark in i^th subject.

For each case, print the case number and the best average grade you can have. Errors less than 10^-6 will be ignored.

Dataset is huge, use faster I/O methods.