버튼을 누르는 두 로봇

시간 제한5초메모리 제한512 MB

요약

1번 버튼에서 시작한 두 로봇이 정해진 순서대로 버튼을 누르도록 매초 이동과 누르기를 배정하고 전체 최소 시간을 구합니다.

난이도: 쉬움10점 중 3점
유형: 시뮬레이션, 그리디
정답자: 아직 제출이 없습니다

문제

주황 로봇과 파란 로봇은 사이좋은 친구다. 사악한 컴퓨터가 둘을 서로 다른 복도에 가두고 시험을 낸다. 시험을 통과하면 케이크를 줄지도 모른다.

복도마다 1부터 100까지 번호가 붙은 버튼이 100개 있다. 버튼 $k$ 는 복도 입구에서 $k$ 미터 떨어진 자리에 있고, 두 로봇은 모두 버튼 1 앞에서 출발한다. 1초 동안 로봇은 어느 방향으로든 1미터를 걷거나, 서 있는 자리의 버튼을 한 번 누르거나, 그 자리에 그대로 서 있는다. 시험을 통과하려면 정해진 버튼을 정해진 순서대로 눌러야 한다. 두 로봇은 순서 전체를 미리 알고 있다. 두 로봇이 순서를 끝내는 데 걸리는 최소 시간을 구하라.

예를 들어 눌러야 하는 순서가 O 2, B 1, B 2, O 4라고 하자. O 2는 주황 로봇 복도의 버튼 2, B 1은 파란 로봇 복도의 버튼 1을 뜻한다. 이 순서는 아래 전략으로 6초에 끝낼 수 있다.

Time | Orange           | Blue
-----+------------------+------------------
  1  | Move to button 2 | Stay at button 1
  2  | Push button 2    | Stay at button 1
  3  | Move to button 3 | Push button 1
  4  | Move to button 4 | Move to button 2
  5  | Stay at button 4 | Push button 2
  6  | Push button 4    | Stay at button 2

파란 로봇은 주황 로봇이 O 2를 다 누를 때까지 기다린 뒤에야 B 1을 누를 수 있다.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다.

각 테스트 케이스는 한 줄이다. 줄은 눌러야 하는 버튼의 개수 $N$ 으로 시작하고, 그 뒤에 $R_i\ P_i$ 꼴의 항이 $N$ 개 이어진다. $R_i$ 는 로봇의 색으로 항상 O 또는 B이고, $P_i$ 는 버튼 번호다.

제한

$1 \le T \le 100$
$1 \le N \le 100$
모든 $i$ 에 대해 $1 \le P_i \le 100$

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 주어진 버튼을 순서대로 모두 누르는 데 필요한 최소 시간(초)이다.

예제5

예제 1

입력

3
4 O 2 B 1 B 2 O 4
3 O 5 O 8 B 100
2 B 2 B 1

예상 출력

Case #1: 6
Case #2: 100
Case #3: 4

예제 2
입력
```
1
1 O 1
```
예상 출력
```
Case #1: 1
```
예제 3
입력
```
1
1 B 100
```
예상 출력
```
Case #1: 100
```
예제 4
입력
```
1
3 O 5 O 5 O 5
```
예상 출력
```
Case #1: 7
```
예제 5
입력
```
1
4 O 100 B 100 O 1 B 1
```
예상 출력
```
Case #1: 201
```