Problem K
Toll Booths

Photo by KRoock74. Retrieved from Wikimedia Commons. CC BY-SA 3.0. Source

You’re getting ready to take a tour of Space School of Mines, a new branch of Colorado School of Mines, when you look at your tourist’s guide and notice that you will pass through several toll booths on the flight there. You pull out your container of BlasterBucks (the local space currency) and get ready to pay up.

But, while looking at your tourist’s guide, you notice something interesting. Some of the tolls are asking for payments of BlasterBucks, but some of the tolls are giving away BlasterBucks!

Your tourist’s guide tells you the order of the tolls you will encounter, and how much each one is asking for or giving away (your input).

You need to make sure that whenever you reach a toll that is asking for BlasterBucks, you have enough to pay the toll. What is the minimum number of BlasterBucks that you can start with that will let you pass through all the tolls in order?

Input

The first line of input is a single number $N$, representing the total number of toll booths. For all inputs, $1 \leq N \leq 10\, 000$.

The following $N$ lines of input are each of the sequential toll booths. Each toll booth is represented by a letter followed by a number, $1 \leq A \leq 1\, 000$, with a space in between. The letter can be a “T” or a “G”, indicating that the toll is either taking or giving BlasterBucks, respectively. The number, $A$, is the amount being taken or given.

Output

Your output should be a single number, indicating the minimum non-negative number of credits that you need to bring with you to pass through all of the toll booths in order.

3
T 1
T 2
T 3

6

4
G 8
T 8
G 9
T 10

1

2
T 1
G 100

1