To welcome attendees to a developers' conference on Jupiter's moon of Io, the organizers inflated many giant beach balls. Each ball is in roughly the shape of either a ~1~ or a ~0~, since those look sort of like the letters I and O. The conference just ended, and so now the beach balls need to be cleaned up. Luckily, the beach ball cleanup robot, BALL-E, is on the job!

The conference was held on an infinite horizontal line, with station ~0~ in the middle, stations ~1, 2, \dots~ to the right, and stations ~-1, -2, \dots~ to the left. Station 0 contains the conference's only beach ball storage warehouse. Each other station contains at most one beach ball.

BALL-E has two storage compartments, each of which can hold a single beach ball. One compartment can only hold ~1~-shaped balls and the other can only hold ~0~-shaped balls. (The ~1~-shaped balls are more oblong than the ~0~-shaped balls, so neither shape of ball will fit in the other shape's compartment.)

BALL-E initially has both the ~0~ and ~1~ compartments empty, and it starts off at station ~0~. The robot can do the following things:

• Move left one station or right one station. This costs 1 unit of power.
• If there is a ball at the current station, and BALL-E is not already storing a ball of that shape, it can put the ball in the appropriate compartment. This takes 0 units of power.
• If there is a ball at the current station, BALL-E can compress it so that its shape becomes the other shape. That is, a ~1~-shaped ball becomes a ~0~-shaped ball, or vice versa. It takes ~C~ units of power to do this. Note that BALL-E may not change the shape of a ball that it has already put into one of its compartments.
• If BALL-E is at station 0 and is storing at least one ball, it can deposit all balls from its compartment(s) into the beach ball storage warehouse. This takes 0 units of power and leaves both compartments empty.

Notice that if BALL-E moves to a station and there is a ball there, BALL-E is not required to pick it up immediately, even if the robot has an open compartment for it. Also, if BALL-E moves to the station with the warehouse, it is not required to deposit any balls it has.

Find the minimum number of units of power needed for BALL-E to transfer all of the balls to the warehouse, using only the moves described above.

Input Specification

The first line of the input gives the number of test cases, ~T~. ~T~ test cases follow. The first line of each test case contains two integers, ~N~ and ~C~: the number of balls and the amount of power units needed to change the shape of a ball, respectively. The next ~N~ lines describe the positions (i.e., station numbers) and the shapes of the balls. The ~i^\text{th}~ line contains two integers, ~X_i~ and ~S_i~: the position and the shape of the ~i^\text{th}~ ball, respectively.

Output Specification

For each test case, output one line containing Case #x: y, where ~x~ is the test case number (starting from 1) and ~y~ is the minimum number of units of power needed to transfer all of the balls to the warehouse, as described above.

Limits

Time limit: 40 seconds.

Memory limit: 1 GB.

~1 \le T \le 100~.

~0 \le S_i \le 1~, for all ~i~.

~-10^9 \le X_i \le 10^9~, for all ~i~.

~0 \le C \le 10^9~.

~X_i ≠ 0~, for all ~i~.

All ~X_i~ are distinct.

Test Set 1

For at most 15 cases:

~1 \le N \le 5\,000~.

For the remaining cases:

~1 \le N \le 100~.

Test Set 2

For at most 15 cases:

~1 \le N \le 10^5~.

For the remaining cases:

~1 \le N \le 5\,000~.

Sample Input

4
5 0
3 0
6 0
8 0
10 1
15 1
5 10
3 0
6 0
8 0
10 1
15 1
5 1
3 0
6 0
8 0
10 1
15 1
2 0
1000000000 0
-1000000000 1

Sample Output

Case #1: 52
Case #2: 56
Case #3: 54
Case #4: 4000000000

In Sample Case #1 (illustrated in the statement), there are ~N = 5~ balls and ~C = 0~. One optimal strategy is to make three round trips from (and back to) the warehouse:

• First round trip: Move to station ~3~, pick up the ~0~ ball there and store it in the ~0~ compartment, move back to station ~0~, and deposit the ball in the warehouse. This takes ~6~ units of power.
• Second round trip: Move to station ~8~, pick up the ~0~ ball there, and store it in the ~0~ compartment. Move to station ~6~, change the ~0~ ball there into a ~1~ ball, and pick it up and store it in the ~1~ compartment. Move to station ~0~ and deposit both balls in the warehouse. This takes ~16~ units of power. (Recall that in this case, it takes ~0~ units of power to change a ball's shape.)
• Third round trip: Move to station ~10~. Change the ~1~ ball there into a ~0~ ball, and pick it up and store it in the ~0~ compartment. Move to station ~15~. Pick up the ~1~ ball there and store it in the ~1~ compartment. Move to station ~0~ and deposit both balls in the warehouse. This takes ~30~ units of power.

The total number of units of power needed to collect all the balls is ~52~.

Sample Case #2 is like Sample Case #1, but now with ~C = 10~. Now BALL-E has to use at least ~56~ units of power:

• First round trip: Get the ball from station ~3~. This takes ~6~ units of power.
• Second round trip: Get the differently-shaped balls from stations ~6~ and ~10~. (These are a ~0~ and a ~1~, respectively, so there is no need to change the shape of either of them.) This takes ~20~ units of power.
• Third round trip: Get the differently-shaped balls from stations ~8~ and ~15~. This takes ~30~ units of power.

Sample Case #3 is also like Sample Case #1, but now with ~C = 1~. Here, BALL-E needs at least ~54~ units of power:

• First round trip: Get the ball from station ~3~. This takes ~6~ units of power.
• Second round trip: Get the ball from station ~8~. When passing through station ~6~ on the way back, change the shape of the ball there and get it. This takes ~17~ units of power.
• Third round trip: Do the same with the balls at stations ~15~ and ~10~. This takes ~31~ units of power.

In Sample Case #4, one optimal strategy is for BALL-E to move to station ~-1\,000\,000\,000~, get the ~1~ ball there, move to station ~1\,000\,000\,000~, get the ~0~ ball there, and then return to station ~0~ to deposit both of them.