Migrated from Lutece 570 D hours

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Streets in City Line lie on one line, one by one. Standy wants to take a tour in City Line within $D$ hours. Before visit, Standy got the map. There are $N+1$ crossings connected by $N$ roads. He can start from and end at any crossing.

Sightseeing on any road takes ONE hour. After passing each road, Standy gets a happiness score. The more happiness score he gets, the happier he is. It's boring to visit a road more than once. For the $k_{th}$ time Standy visits the $i_{th}$ road, the happiness score he gets is

$a_i-(k-1)\times b_i$

Now please give Standy a plan to make him be the happiest man on earth.

Input

There are multiple test cases. The first line of the input will be an integer $T$ ($T \leq 30$) indicating the number of test cases.

For each test case there are two integers $N$ and $D$ ($1 \leq N, D \leq 100$) in a single line, representing the number of roads in City Line and the time of the tour. For the following $N$ lines, each line lists $a_i$ and $b_i$. $1 \leq a_i, b_i \leq 10^6$, $a_i - (D-1) \times b_i \geq 0$.

Output

For each test case, print Case #t: first, in which t is the number of the test case starting from $1$. Then output the maximum happiest score you can get.

Samples

1
2 3
2 1
3 1

Case #1: 7

Note

Route crossing 1 -> crossing 2 -> crossing 3 -> crossing 2 gets the highest score.

Resources

10th UESTC Programming Contest Final