407345: GYM102769 E Exam Results

Memory Limit:512 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Exam Resultstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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?

Input

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$$$.

Output

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.

ExampleInput
2
2 50
2 1
5 1
5 60
8 5
9 3
14 2
10 8
7 6
Output
Case #1: 2
Case #2: 4

加入题单

上一题 下一题 算法标签: