Page not loading? Try clicking here.
Placeholder

#10438

I, O Bot 40s 1024MB

Problems

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.

Illustration of Sample Cases 1, 2, and 3.

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 \mathbf{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

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


Output

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.


Example 

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
Case #1: 52
Case #2: 56
Case #3: 54
Case #4: 4000000000
In Sample Case #1 (illustrated in the statement), there are \mathbf{N} = 5 balls and \mathbf{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 \mathbf{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 \mathbf{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 -1000000000, get the 1 ball there, move to station 1000000000, get the 0 ball there, and then return to station 0 to deposit both of them.

Source

GCJ 2022r2 D

You must sign in to write code.