페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#10438

I, O 봇 40s 1024MB

문제

목성의 위성 이오(Io)에서 열린 개발자 컨퍼런스에 참석자들을 맞이하기 위해, 주최 측은 거대한 비치볼을 많이 불어 놓았다. 각 공은 대략 1 또는 0 모양인데, 이는 글자 I와 O처럼 보이기 때문이다. 컨퍼런스가 막 끝났고, 이제 비치볼을 치워야 한다. 다행히 비치볼 청소 로봇 BALL-E가 이 일을 맡고 있다!

컨퍼런스는 무한한 수평선 위에서 열렸고, 가운데에 정거장(station) 0이 있으며, 오른쪽에는 1, 2, \dots, 왼쪽에는 -1, -2, \dots 정거장들이 있다. 정거장 0에는 컨퍼런스의 유일한 비치볼 보관 창고(warehouse)가 있다. 그 외의 각 정거장에는 비치볼이 최대 하나까지 있을 수 있다.

Illustration of Sample Cases 1, 2, and 3.

BALL-E에는 저장 칸(storage compartment)이 두 개 있고, 각 칸에는 비치볼 하나만 담을 수 있다. 한 칸은 1 모양 공만 담을 수 있고, 다른 칸은 0 모양 공만 담을 수 있다. (1 모양 공은 0 모양 공보다 더 길쭉해서, 서로의 칸에 들어가지 않는다.)

BALL-E는 처음에 0 칸과 1 칸이 모두 비어 있는 상태로 정거장 0에서 시작한다. 로봇은 다음 행동들을 할 수 있다:

  • 왼쪽으로 한 정거장 또는 오른쪽으로 한 정거장 이동한다. 이는 전력 1을 소모한다.
  • 현재 정거장에 공이 있고, BALL-E가 그 모양의 공을 아직 보관하고 있지 않다면, 그 공을 해당 칸에 넣을 수 있다. 이는 전력을 0 소모한다.
  • 현재 정거장에 공이 있다면, 그 공을 압축하여 반대 모양으로 바꿀 수 있다. 즉 1 모양 공은 0 모양 공이 되고, 그 반대도 가능하다. 이를 수행하는 데 전력 \mathbf{C}를 소모한다. 단, BALL-E가 이미 자신의 칸에 넣어 둔 공의 모양은 바꿀 수 없다.
  • BALL-E가 정거장 0에 있고 하나 이상의 공을 보관 중이라면, 보관 중인 모든 공을 창고에 한 번에 내려놓을 수 있다. 이는 전력을 0 소모하며 두 칸을 모두 비운다.

BALL-E가 어떤 정거장으로 이동했을 때 공이 그곳에 있더라도, 해당 모양의 빈 칸이 있다고 해서 즉시 집어야 하는 것은 아니다. 또한 BALL-E가 창고가 있는 정거장에 도착하더라도, 보관 중인 공을 반드시 내려놓아야 하는 것은 아니다.

위에서 설명한 행동들만 사용하여 모든 공을 창고로 옮기기 위해 필요한 전력 소모량의 최솟값을 구하라.


입력

입력의 첫 줄에는 테스트 케이스 수 \mathbf{T}가 주어진다. \mathbf{T}개의 테스트 케이스가 이어진다.
각 테스트 케이스의 첫 줄에는 정수 두 개 \mathbf{N}, \mathbf{C}가 주어진다. 이는 각각 공의 개수와 공의 모양을 바꾸는 데 필요한 전력 소모량이다.
그 다음 \mathbf{N}줄이 공들의 위치(정거장 번호)와 모양을 나타낸다. 이 중 i번째 줄에는 정수 두 개 \mathbf{X_i}, \mathbf{S_i}가 주어진다. 이는 각각 i번째 공의 위치와 모양이다.


출력

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력하라. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 위에서 설명한 방식으로 모든 공을 창고로 옮기기 위해 필요한 전력 소모량의 최솟값이다.


예제 

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
샘플 케이스 #1(문제 설명에 그림으로 제시됨)에서 \mathbf{N} = 5, \mathbf{C} = 0이다. 한 가지 최적 전략은 창고에서 왕복하는 이동을 세 번 하는 것이다: 첫 번째 왕복: 정류장 3으로 이동해 거기 있는 0공을 가져와 0칸에 보관한 뒤, 정류장 0으로 돌아와 창고에 반납한다. 이는 전력 6을 소모한다. 두 번째 왕복: 정류장 8으로 이동해 0공을 가져와 0칸에 보관한다. 정류장 6으로 이동해 그곳의 0공을 1공으로 바꾸고 1칸에 보관한다. 정류장 0으로 이동해 두 공을 창고에 반납한다. 이는 전력 16을 소모한다. (이 경우 공의 모양을 바꾸는 데 전력이 0이 든다는 점을 기억하라.) 세 번째 왕복: 정류장 10으로 이동해 그곳의 1공을 0공으로 바꾸고 0칸에 보관한다. 정류장 15로 이동해 1공을 가져와 1칸에 보관한다. 정류장 0으로 이동해 두 공을 창고에 반납한다. 이는 전력 30을 소모한다. 모든 공을 모으는 데 필요한 총 전력은 52이다. 샘플 케이스 #2는 샘플 케이스 #1과 비슷하지만 \mathbf{C} = 10이다. 이제 BALL-E는 최소 56의 전력을 사용해야 한다: 첫 번째 왕복: 정류장 3의 공을 가져온다. 전력 6. 두 번째 왕복: 정류장 6과 10의 서로 다른 모양의 공을 가져온다. (각각 0과 1이므로 모양을 바꿀 필요가 없다.) 전력 20. 세 번째 왕복: 정류장 8과 15의 서로 다른 모양의 공을 가져온다. 전력 30. 샘플 케이스 #3도 샘플 케이스 #1과 비슷하지만 \mathbf{C} = 1이다. 여기서는 BALL-E가 최소 54의 전력을 써야 한다: 첫 번째 왕복: 정류장 3의 공을 가져온다. 전력 6. 두 번째 왕복: 정류장 8의 공을 가져온다. 돌아오는 길에 정류장 6을 지나며 그 공의 모양을 바꾸고 가져온다. 전력 17. 세 번째 왕복: 정류장 15와 10의 공에 대해 같은 일을 한다. 전력 31. 샘플 케이스 #4에서는 BALL-E가 정류장 -1000000000으로 이동해 그곳의 1공을 가져오고, 정류장 1000000000으로 이동해 0공을 가져온 다음, 정류장 0으로 돌아와 두 공을 창고에 반납하는 전략이 최적 중 하나이다.

출처

GCJ 2022r2 D

로그인해야 코드를 작성할 수 있어요.