Mountain Road

A narrow mountain road has only a single lane, which makes it a bottleneck for two-way traffic. Cars wait in two queues, one at each end of the road. Your task is to schedule when the waiting cars enter the road so that the moment the last car leaves the road is as early as possible.

Each car is described by three values: the direction it drives, the time it arrives at its end of the road, and the time it needs to drive through the road when no car ahead of it slows it down.

The following rules must be respected:

• A car may not overtake another car on the road, and the order of the cars in each queue may not be changed.
• Two cars traveling in opposite directions can never be on the road at the same time.
• For safety, two cars traveling in the same direction may not pass any point of the road within less than 10 seconds of one another, so that a following car cannot crash into the car in front if it brakes suddenly. However, if a car traveling in the opposite direction passes in between, the road is known to have been empty, and this 10-second rule does not apply to the next same-direction car.

The first line contains an integer $c$ ($1 \le c \le 200$), the number of test cases.

Each test case starts with a line containing an integer $n$ ($1 \le n \le 200$), the number of cars. Each of the following $n$ lines describes one car with an uppercase letter, either A or B, giving the direction the car travels, followed by two integers $t$ ($0 \le t \le 100000$) and $d$ ($1 \le d \le 100000$): the time the car arrives at its end of the road and the minimum time it needs to drive through the road, both in seconds.

Within a test case the cars are listed in order of increasing arrival time, and no two cars arrive at the same time.

For each test case, print a single line containing the earliest time, in seconds, at which the last car leaves the road when all cars are scheduled optimally.