시간 제한메모리 제한제출정답맞힌 사람정답 비율
40 초 (추가 시간 없음) 1024 MB1311100.000%

문제

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

입력

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.

출력

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.

제한

  • $1 \le \mathbf{T} \le 100$.
  • $0 \le \mathbf{S_i} \le 1$, for all $i$.
  • $-10^9 \le \mathbf{X_i} \le 10^9$, for all $i$.
  • $0 \le \mathbf{C} \le 10^9$.
  • $\mathbf{X_i} ≠ 0$, for all $i$.
  • All $\mathbf{X_i}$ are distinct.

Test Set 1 (11점)

For at most 15 cases:

  • $1 \le \mathbf{N} \le 5000$.

For the remaining cases:

  • $1 \le \mathbf{N} \le 100$.

Test Set 2 (20점)

For at most 15 cases:

  • $1 \le \mathbf{N} \le 10^5$.

For the remaining cases:

  • $1 \le \mathbf{N} \le 5000$.

예제 입력 1

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

예제 출력 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.

출처

Contest > Google > Code Jam > Google Code Jam 2022 > Round 2 D번

채점 및 기타 정보

  • 예제는 채점하지 않는다.