I, O 봇

목성의 위성 Io에서 열리는 개발자 회의의 참석자들을 환영하기 위해, 주최 측은 수많은 거대한 비치볼을 부풀렸다. 각 공은 대략 $1$ 또는 $0$ 모양인데, 이 모양들이 각각 문자 I와 O를 어느 정도 닮았기 때문이다. 회의가 막 끝났으므로 이제 비치볼을 정리해야 한다. 다행히 비치볼 정리 로봇인 BALL-E이 이 일을 맡았다!

회의는 무한한 수평선 위에서 열렸으며, 중앙에는 역 $0$이 있고, 오른쪽에는 역 $1, 2, \dots$이, 왼쪽에는 역 $-1, -2, \dots$이 있다. 역 0에는 회의장의 유일한 비치볼 보관 창고가 있다. 그 밖의 각 역에는 최대 하나의 비치볼이 있다.

BALL-E에는 보관 칸이 두 개 있으며, 각 칸에는 비치볼 하나를 넣을 수 있다. 한 칸에는 $1$ 모양의 공만 넣을 수 있고, 다른 칸에는 $0$ 모양의 공만 넣을 수 있다. ($1$ 모양의 공은 $0$ 모양의 공보다 더 길쭉하므로, 어느 모양의 공도 다른 모양을 위한 보관 칸에는 들어가지 않는다.)

처음에 BALL-E의 $0$ 보관 칸과 $1$ 보관 칸은 모두 비어 있으며, 로봇은 역 $0$에서 출발한다. 로봇은 다음 행동을 할 수 있다:

• 왼쪽이나 오른쪽으로 한 역 이동한다. 이 행동에는 전력 1단위가 든다.

• 현재 역에 공이 있고 BALL-E이 아직 그 모양의 공을 보관하고 있지 않다면, 해당 공을 알맞은 보관 칸에 넣을 수 있다. 이 행동에는 전력 0단위가 든다.

• 현재 역에 공이 있으면, BALL-E은 공을 압축하여 모양을 다른 모양으로 바꿀 수 있다. 즉, $1$ 모양의 공은 $0$ 모양의 공이 되며, 그 반대도 가능하다. 이 행동에는 전력 $\mathbf{C}$단위가 든다. BALL-E은 이미 보관 칸 중 하나에 넣은 공의 모양을 바꿀 수 없다는 점에 유의하라.

• BALL-E이 역 0에 있고 적어도 하나의 공을 보관하고 있다면, 보관 칸에 있는 모든 공을 비치볼 보관 창고에 넣을 수 있다. 이 행동에는 전력 0단위가 들며, 이후 두 보관 칸은 모두 비게 된다.

BALL-E이 어떤 역으로 이동했을 때 그곳에 공이 있더라도, 로봇에게 그 공을 넣을 빈 보관 칸이 있더라도, BALL-E이 즉시 공을 집어야 하는 것은 아니다. 또한 BALL-E이 창고가 있는 역으로 이동하더라도, 보관 중인 공을 반드시 내려놓아야 하는 것은 아니다.

위에서 설명한 행동만 사용하여 BALL-E이 모든 공을 창고로 옮기는 데 필요한 전력 단위 수의 최솟값을 구하라.

제한

시간 제한: 40초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i$에 대해 $0 \le \mathbf{S_i} \le 1$. 모든 $i$에 대해 $-10^9 \le \mathbf{X_i} \le 10^9$. $0 \le \mathbf{C} \le 10^9$. 모든 $i$에 대해 $\mathbf{X_i} ≠ 0$. 모든 $\mathbf{X_i}$은 서로 다르다.

테스트 세트 1 (Visible Verdict)

최대 15개의 케이스에 대해: $1 \le \mathbf{N} \le 5000$. 나머지 케이스에 대해: $1 \le \mathbf{N} \le 100$.

테스트 세트 2 (Hidden Verdict)

최대 15개의 케이스에 대해: $1 \le \mathbf{N} \le 10^5$. 나머지 케이스에 대해: $1 \le \mathbf{N} \le 5000$.

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

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$은 (1부터 시작하는) 테스트 케이스 번호이고, $y$은 위에서 설명한 대로 모든 공을 창고로 옮기는 데 필요한 전력 단위 수의 최솟값이다.

예제 케이스 #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$으로 돌아와 두 공을 모두 내려놓는 것이다.