Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Có một quãng đường rất hẹp chỉ đủ cho một chiếc xe ô tô có thể qua tại một thời điểm. Các xe không thể vượt nhau và cũng thể đi ngược chiều nhau trên quãng đường này. Tại hai đầu của quãng đường (giả sử là đầu A và đầu B) người ta muốn sắp xếp một cách tối ưu các xe ô tô sao cho các xe đều qua được quãng đường này và thời điểm xe cuối cùng kết thúc hành trình là nhỏ nhất. Với mỗi chiếc xe sẽ có ba giá trị là: điểm xuất phát, thời gian bắt đầu đến và tổng thời gian cần thiết để đi qua đường. Để đảm bảo an toàn, hai xe cùng chiều phải đi cách nhau ít nhất 10 giây.  

Ví dụ với 4 xe đến được mô tả là:     

Xe thứ nhất: A 0 60

Xe thứ hai:   B 19 10

Xe thứ ba:    B 80 20

Xe thứ tư:    A 85 100

Ta sẽ có cách sắp xếp tốt nhất là:  Xe thứ nhất đi tại thời điểm 0, xe thứ hai đi tại thời điểm 60, xe thứ ba đi tại thời điểm 80 và xe thứ 5 đi tại thời điểm 100. Thời điểm xe cuối cùng kết thúc hành trình là 100 + 100 = 200.

 Input: Dòng đầu tiên ghi số bộ test, không lớn hơn 200. Mỗi bộ test gồm:

• Dòng đầu tiên ghi số nguyên dương n không lớn hơn 200.
• n dòng tiếp theo ghi thông tin về mỗi chiếc xe trong đó gồm 1 ký tự (A hoặc B) cho biết hướng đi, tiếp theo là hai số nguyên t và d với t là thời điểm đến còn d là thời gian cần thiết (ít nhất) để đi hết quãng đường (t và d không lớn hơn 10⁵)

Chú ý: các ô tô đã được sắp xếp theo thời gian đến tăng dần và không có hai xe nào đến cùng nhau. 

Output: Với mỗi bộ test, output đưa ra một số nguyên duy nhất là thời gian mà chiếc xe cuối cùng đã rời khỏi quãng đường theo cách sắp xếp tối ưu. 

Example

Input:
2
4
A 0 60
B 19 10
B 80 20
A 85 100
4
A 0 100
B 50 100
A 100 1
A 170 100

Output:
200
270

Giải thích test 2:

Xe 2 xuất phát trước.

Xe 1 xuất phát lúc t = 150, đến đích lúc t = 250.

Xe 3 xuất phát lúc t = 160, đến đích lúc t = 260 (d = 1 chỉ là thời gian tối thiểu để đi hết quãng đường).

Xe 4 xuất phát lúc t = 170, đến đích lúc t = 270.