407345: GYM102769 E Exam Results

Professor Alex is preparing an exam for his students now.

There will be $$$n$$$ students participating in this exam. If student $$$i$$$ has a good mindset, he/she will perform well and get $$$a_i$$$ points. Otherwise, he/she will get $$$b_i$$$ points. So it is impossible to predict the exam results. Assume the highest score of these students is $$$x$$$ points. The students with a score of no less than $$$x \cdot p\%$$$ will pass the exam.

Alex needs to know what is the maximum number of students who can pass the exam in all situations. Can you answer his question?

The first line of the input gives the number of test cases, $$$T\ (1 \le T \le 5\times 10^3)$$$. $$$T$$$ test cases follow.

For each test case, the first line contains two integers $$$n\ (1 \le n \le 2 \times 10^5)$$$ and $$$p\ (1 \le p \le 100)$$$, where $$$n$$$ is the number of students and $$$p\%$$$ is the ratio.

Each of the following $$$n$$$ lines contains two integers $$$a_i, b_i\ (1 \le b_i \le a_i \le 10^9)$$$, representing the scores of student $$$i$$$.

The sum of $$$n$$$ in all test cases doesn't exceed $$$5 \times 10^5$$$.

For each test case, output one line containing "Case #x: y", where $$$\texttt{x}$$$ is the test case number (starting from $$$1$$$), and $$$\texttt{y}$$$ is the maximum number of students.

2
2 50
2 1
5 1
5 60
8 5
9 3
14 2
10 8
7 6

Case #1: 2
Case #2: 4