I, O Bot

주피터의 위성 이오에서 열린 개발자 컨퍼런스 참석자를 맞이하려고 주최 측이 거대한 비치볼을 여러 개 불었습니다. 각 공은 대략 $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단위가 든다.
• 현재 역에 공이 있다면, 그 공을 압축해 모양을 반대 모양으로 바꿀 수 있다. 즉 $1$ 모양 공은 $0$ 모양 공이, $0$ 모양 공은 $1$ 모양 공이 된다. 이때 전력 $C$단위가 든다. 다만 BALL-E가 이미 보관칸에 넣은 공의 모양은 바꿀 수 없다.
• BALL-E가 역 0에 있고 공을 하나 이상 보관하고 있다면, 보관칸의 모든 공을 창고에 맡길 수 있다. 전력은 0단위가 들며, 두 보관칸은 모두 비게 된다.

로봇이 어느 역에 도착했을 때 그곳에 공이 있고 보관칸이 비어 있더라도, 반드시 그 자리에서 공을 집어야 하는 것은 아닙니다. 또 창고가 있는 역에 도착했다고 해서 가지고 있는 공을 반드시 맡겨야 하는 것도 아닙니다.

위의 동작만 사용해 모든 공을 창고로 옮기는 데 필요한 전력의 최솟값을 구하십시오.

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어집니다. 이어서 $T$개의 테스트 케이스가 주어집니다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $C$가 주어집니다. $N$은 공의 개수, $C$는 공의 모양을 바꾸는 데 필요한 전력 단위입니다. 이어지는 $N$개의 줄은 공의 위치(역 번호)와 모양을 나타냅니다. $i$번째 줄에는 두 정수 $X_i$와 $S_i$가 주어집니다. $X_i$는 $i$번째 공의 위치, $S_i$는 그 모양입니다.

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

• $1 \le T \le 100$.
• 모든 $i$에 대해 $0 \le S_i \le 1$.
• 모든 $i$에 대해 $-10^9 \le X_i \le 10^9$.
• $0 \le C \le 10^9$.
• 모든 $i$에 대해 $X_i \ne 0$.
• 모든 $X_i$는 서로 다르다.

샘플 케이스 #1(문제 설명에 그림으로 나온 경우)에는 공이 $N = 5$개 있고 $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과 같지만 $C = 10$입니다. 이때 BALL-E는 최소 $56$단위의 전력을 써야 합니다.

• 첫 번째 왕복: 역 $3$의 공을 가져옵니다. 전력 $6$단위가 듭니다.
• 두 번째 왕복: 역 $6$과 역 $10$에서 모양이 서로 다른 공을 가져옵니다. (각각 $0$과 $1$이므로 어느 공의 모양도 바꿀 필요가 없습니다.) 전력 $20$단위가 듭니다.
• 세 번째 왕복: 역 $8$과 역 $15$에서 모양이 서로 다른 공을 가져옵니다. 전력 $30$단위가 듭니다.

샘플 케이스 #3도 샘플 케이스 #1과 같지만 $C = 1$입니다. 여기서 BALL-E는 최소 $54$단위의 전력이 필요합니다.

• 첫 번째 왕복: 역 $3$의 공을 가져옵니다. 전력 $6$단위가 듭니다.
• 두 번째 왕복: 역 $8$의 공을 가져옵니다. 돌아오는 길에 역 $6$을 지날 때 그 공의 모양을 바꾸고 가져옵니다. 전력 $17$단위가 듭니다.
• 세 번째 왕복: 역 $15$와 역 $10$의 공에 대해 같은 방식을 적용합니다. 전력 $31$단위가 듭니다.

샘플 케이스 #4에서 최적 전략 중 하나는 BALL-E가 역 $-1000000000$으로 이동해 그곳의 $1$ 공을 가져오고, 역 $1000000000$으로 이동해 그곳의 $0$ 공을 가져온 뒤, 역 0으로 돌아와 두 공을 모두 맡기는 것입니다.