외길 산악 도로

좁은 산악 도로에 차선이 하나뿐이라 양방향 통행의 병목이 된다. 자동차들은 도로의 양쪽 끝에서 각각 줄을 서서 기다린다. 기다리는 자동차들이 언제 도로에 진입할지 정하여 마지막 자동차가 도로를 빠져나가는 시각을 가능한 한 이르게 만드는 것이 목표다.

각 자동차는 세 가지 값으로 주어진다. 진행 방향, 자기 쪽 도로 끝에 도착하는 시각, 그리고 앞차에게 방해받지 않을 때 도로를 통과하는 데 걸리는 시간이다.

다음 규칙을 지켜야 한다.

• 도로 위에서 다른 차를 추월할 수 없으며, 각 줄에 서 있는 자동차들의 순서를 바꿀 수 없다.
• 서로 반대 방향으로 가는 두 자동차는 절대로 동시에 도로 위에 있을 수 없다.
• 안전을 위해 같은 방향으로 가는 두 자동차는 도로의 어느 지점도 10초 미만의 간격으로 지날 수 없다. 이는 앞차가 급제동하더라도 뒤차가 추돌하지 않도록 하기 위함이다. 다만 그 사이에 반대 방향 자동차가 지나갔다면 도로가 비어 있었음이 확인되므로, 다음 같은 방향 자동차에는 이 10초 규칙이 적용되지 않는다.

첫째 줄에 테스트 케이스의 수 $c$ ($1 \le c \le 200$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 자동차의 수 $n$ ($1 \le n \le 200$)이 주어진다. 이어지는 $n$개의 줄에는 각 자동차의 정보가 주어지는데, 먼저 진행 방향을 나타내는 대문자 A 또는 B가 오고 그다음 두 정수 $t$ ($0 \le t \le 100000$)와 $d$ ($1 \le d \le 100000$)가 온다. $t$는 자동차가 자기 쪽 도로 끝에 도착하는 시각, $d$는 도로를 통과하는 데 필요한 최소 시간이며 둘 다 초 단위이다.

한 테스트 케이스 안에서 자동차들은 도착 시각이 증가하는 순서로 주어지며, 도착 시각이 같은 자동차는 없다.

각 테스트 케이스마다 모든 자동차를 최적으로 배치했을 때 마지막 자동차가 도로를 빠져나가는 가장 이른 시각을 초 단위로 한 줄에 출력한다.