Cô bò Bessie đang thi đấu môn trượt tuyết băng đồng tại Thế vận hội Moolympic mùa đông. Ban đầu, cô di chuyển với vận tốc \(1\) mét mỗi giây. Tuy nhiên, theo thời gian cô ngày càng mệt và bắt đầu chậm lại. Mỗi lần Bessie chậm lại, vận tốc của cô giảm: sau lần đầu tiên, cô di chuyển với vận tốc \(1/2\) mét mỗi giây; sau hai lần, cô di chuyển với vận tốc \(1/3\) mét mỗi giây; và cứ tiếp tục như vậy.

Bạn được cho biết thời điểm và vị trí Bessie chậm lại dưới dạng một chuỗi sự kiện. Một sự kiện như

T 17

có nghĩa là Bessie chậm lại tại một thời điểm cụ thể, ở đây là sau khi cuộc đua bắt đầu \(17\) giây. Một sự kiện như

D 10

có nghĩa là Bessie chậm lại tại một khoảng cách cụ thể tính từ điểm xuất phát, trong trường hợp này là \(10\) mét.

Cho danh sách \(N\) sự kiện như vậy (\(1 \le N \le 10\,000\)), hãy tính thời gian tính bằng giây để Bessie đi hết một kilômét. Làm tròn đáp án đến số giây nguyên gần nhất; \(0{,}5\) được làm tròn lên \(1\).

Dữ liệu vào

• Dòng đầu tiên chứa \(N\).
• \(N\) dòng tiếp theo, mỗi dòng có dạng T x hoặc D x, lần lượt biểu thị một sự kiện theo thời gian hoặc theo khoảng cách. Trong cả hai trường hợp, \(x\) là một số nguyên và sự kiện được đảm bảo xảy ra trước khi Bessie đi đủ tổng quãng đường một kilômét. Nhiều sự kiện có thể xảy ra đồng thời, khiến Bessie chậm đi đáng kể cùng một lúc. Các sự kiện có thể không được liệt kê theo thứ tự.

Ràng buộc

• \(1 \le N \le 10\,000\).
• Mỗi \(x\) là một số nguyên và sự kiện tương ứng xảy ra trước khi Bessie đi được một kilômét.

Dữ liệu ra

In ra tổng thời gian cần thiết để Bessie đi được \(1\) kilômét, làm tròn đến số giây nguyên gần nhất với trường hợp đúng nửa giây được làm tròn lên.

Ví dụ

2
T 30
D 10

2970

Nguồn

USACO 2014 January Contest, Silver — Problem 1: Bessie Slows Down

Tác giả: Brian Dean, 2014.